티스토리 뷰
아이템 납품 컨텐츠
게임을 하다 보면 생활컨텐츠를 즐기는 경우도 있다.
그런 생활 컨텐츠 중, 이벤트성 컨텐츠는 특정 아이템을 NPC에게 납품해 일정 점수를 얻을 수 있고
그 점수를 모아 일정 순위 안에 들면 보상을 받을 수 있다.
파이널 판타지를 같이 즐기는 지인에게 문의가 왔다.
"혹시, 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묶음 이런식으로 조건을 걸고서도 해를 구할 수 있으니 충분히 쓸 만한 것 같다.
'알고리즘' 카테고리의 다른 글
| Monotone Chain 알고리즘(볼록 껍질, Convex Hull) (0) | 2019.07.30 |
|---|