티스토리 뷰

아이템 납품 컨텐츠

게임을 하다 보면 생활컨텐츠를 즐기는 경우도 있다.

 

그런 생활 컨텐츠 중, 이벤트성 컨텐츠는 특정 아이템을 NPC에게 납품해 일정 점수를 얻을 수 있고

그 점수를 모아 일정 순위 안에 들면 보상을 받을 수 있다.

 

파이널 판타지 XIV - Online, 창천 거리 부흥 납품 테이블

파이널 판타지를 같이 즐기는 지인에게 문의가 왔다.

 

"혹시, 10점, 32점, 35점의 아이템들을 적당히 납품해서 내 점수를 1234567점으로 만들 수 있을까?"

 

전부 다 짝수도 아니고 $GCD(10, 32, 35) = 1$이므로 모든 숫자를 완성할 수 있다. 따라서, 가능하다고 답해줬다.

(글로벌 쿨 다운 아닙니다)

 

 

 

"그럼, 10점, 32점, 35점 아이템을 몇 개 납품해야하는지 계산해주는 프로그램 만들어줘"

 

문제 분석

해결해야하는 문제는 간단하다. 바로 아래의 식을 만족하는 $x, y, z$ 값을 구하면 된다.

$$10x+32y+35z = m (m, x, y, z \in Z)$$

 

이 문제는 매우 유명한 문제로, 디오판토스 방정식을 해결하면 위의 모든 조건을 만족하는 정수해의 일반해를 찾을 수 있다.

 

조건을 추가하자면 $x, y, z$ 모두 0 이상인 정수여야 한다는 조건이 추가된다.

 

미지수가 3개이므로 $10x+35z=5p$로 치환할 수 있다. 최대공약수가 5이므로 양변을 모두 5로 나눠주면 다음과 같은 식을 얻는다.

 

$$ 2x+7z=p $$

 

위 식의 일반해를 구하면, $x=4p, z=-p$임을 알 수 있다. 항이 2개인 1차 디오판토스 방정식의 일반해를 구하면 $L$이 임의의 정수일 때, $x=4p+7L, z=-2L-p$이다.

 

그리고, 마찬가지로 $5p+32y=m$도 마찬가지로 일반해를 구해 해결해주자.

 

일반해를 구하면 $p=13m-32k, y=5k-2m$임을 알 수 있다. 여기서 구한 $p$를 각각 $x, z$에 대입하면 다음과 같은 식을 얻을 수 있다.

 

$$x=52m-128k+7L, y=5k-2m, z=32k-13m-2L$$

 

$m$은 달성하고자 하는 목표이므로 상수이다. 따라서 정해져 있으므로 $k, l$에 임의의 정수를 대입하면 우리가 원하는 $x, y, z$를 얻을 수 있다.

 

그런데, 게임 아이템이 음수 개 있을 수는 없잖아?

그렇다. 게임 아이템은 음수 개 일 수 없다. 따라서, $x, y, z$가 모두 0보다 큰 값을 가져야 하고, 이 식을 위해 아까 구한 $k, l$에 관한 식을 이용해 연립 부등식을 풀면 $k, l$의 부등식의 영역을 얻을 수 있다.

 

예제로, $m=123344$이면, 다음과 같은 구역 내의 $k, l$을 사용해 식에 대입하면, 반드시 $x, y, z$의 값이 0 이상이 나온다.

연립 부등식의 해

저 초록 선과 빨간 선의 사이에 있는 아주 얇고 길쭉한 삼각형이 우리가 찾는 해가 존재하는 구간이다.

 

다음은, 그 성질을 이용해 구한 $x, y, z$ 값들의 일부이다.

 

(  1411, 1377, 1862 )
(  1418, 1377, 1860 )
(  1425, 1377, 1858 )
(  1432, 1377, 1856 )
(  1439, 1377, 1854 )
(  1446, 1377, 1852 )
(  1453, 1377, 1850 )
(  1460, 1377, 1848 )
(  1467, 1377, 1846 )
(  1474, 1377, 1844 )
(  1481, 1377, 1842 )
(  1488, 1377, 1840 )

 

어느 튜플을 $10x+32y+35z = m$에 대입하더라도 $m=123334$라는 값을 얻을 수 있다.

 

디오판토스 방정식을 이용하면, 적당한 납품 개수를 찾아 점수 아트를 해낼 수 있다.

 

물론, 위의 예제는 35개의 납품 개수가 비정상적으로 많은데.. 왜 비정상적인지는 디아뎀에서 35점짜리 아이템을 캐보면 알 수 있다.

 

하지만, 35점짜리 아이템 9묶음 이런식으로 조건을 걸고서도 해를 구할 수 있으니 충분히 쓸 만한 것 같다.

 

계산기 : shieldnet.github.io/vue_training/#/

댓글
댓글쓰기 폼
공지사항
Total
21,136
Today
0
Yesterday
27
링크
TAG
more
«   2022/07   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
글 보관함