구슬게임(Dynamic Programming 유형)
: 다이나믹 프로그래밍(동적 계획법)의 기초가되는 문제라서 풀어봤다.
- 동적계획법 문제를 풀 때는, 사실 문제를 낼 때 "이건 동적 계획법 문제니다."라고 하지는 않으므로, 내가 찾아내야하는데, 이 문제는 구슬의 개수 범위가 1,000,000이라는 점을 토대로 일단 제일 처음 접근해볼 수 있는 해결책인 '완전탐색(brute-force)'가 통하지 않는다는 것을 알아채야한다.
- 구슬이 백만개로 주어진다면, 이걸 완전탐색으로 풀려면, 실제로 1,2,3 개씩 가져갈 수 있으므로, 둘의 모든 케이스를 분석하려면 31,000,000의 시행을 해야한다. 뿐만 아니라 사실 이문제의 조건인 '둘다 최선을 다한다'는 조건 자체에서 완전 탐색법을 쓰는건 의미가 없음을 알 수 있다. 그 이유는 실제로 철수는 구슬 4개인 상황에서 질 수 밖에 없는데, 그 이유는 1,2,3 어떤 개수를 가져가도 영희에게 필승법(?)이 있기 때문이다. 하지만, 완전탐색의 경우 철수1개, 영희2개, 철수1개 처럼 철수가 이기는(즉, 영희가 최선을 다하지 않는) 모든 경우를 탐색할 것이기에 사실상 의미가 없다.
- 그렇게 완전탐색법으로 풀 수 없는 문제라는 것을 알았다면 ? 이제 다른 해결책을 찾아봐야한다(당연히..ㅎ). 그중에서도 어떤 규칙이 있지 않을까라는 관점에서 n= 0, 1, 2, 3, 4, 5,.. 이렇게 처음부터 (bottom to top)접근해 나가면서 규칙을 찾아봐야겠다는 생각 혹은 행동을 하고 있다면, 동적계획법을 나름 체화했다고 볼 수 있을 것 같다
[동적계획법의 대한 대략적인 플로우]
1) 부분 문제를 정의한다. 즉, 무슨 값을 구할지를 정의한다.
2) 점화식을 구한다. 즉, 그 값을 어떻게 구할지에 대한 식을 세운다.
3) 당연하지만, 문제를 해결한다. 즉, 실제로 코드를 짠다.
문제 풀이
1) 부분 문제를 정의한다. 즉, 무슨 값을 구할지를 정의한다
: 우리가 원하는 것은 '철수가 이길 수 있는지 없는지(True or False)'이다. 따라서, 우리는 철수가 이길 수 있는지 없는지를 구하기로 결정한다.
2) 부분으로 나눈 문제를 합쳐서 어떻게 전체 문제를 해결할지를 결정한다.
: 그럼 실제로 정의한 문제를 어떻게 풀지에 대한 식을 세워야한다. 나는 개인적으로 이부분을 '규칙을 찾아내야한다'라고 표현하고 싶다. 그러면 실제로 규칙을 찾아보면 먼저, 철수의 승패여부를 리턴하는 식을 'T(N) N=구슬의 개수(0<=N<=1,000,000' 라고 해보자
T(0) = 구슬이 0개면 철수는 이길 수 없다 = False T(1) = 구슬이 1개면 철수는 바로 1개를 가져가버리면 이길 수밖에 없다 = True T(2), T(3)까지 마찬가지로 이길 수밖에 없다 = True T(4) = 1을 먼저 가져가면 최선을 다하는 영희는 3을 가져갈 것이고 2를 먼저 가져가면 영희는 2를 3을 먼저 가져가면 영희는 1을 가져가서 철수는 이길 수 없다 = False
: 사실 여기서부터 동적계획법이든 이런 유형의 문제를 많이 풀어봤다면, 뭔가 '느낌'이 와야한다..ㅎㅎ T(4)를 구할 때, 철수가 한개를 가져가면 3개가 남는데, 3개가 남았을 때 승패여부를 판단하는 것은 T(3)에서 했었다. 그러면 T(3)이 True였으니까 결국 영희는 필승법을 가진셈이다. 또한, 2를 가져가도 T(2), 3을 가져가도 T(1)이 모두 True이기에 영희가 이길 수밖에 없다. 그러면 좀더 해보자.
T(5) = 1을 먼저 가져가면 남은 4개 T(4)=False => 철수가 이긴다 T(6) = 1을 먼저 가져가면 남은 5개 T(5)=True =>영희가 이긴다 2를 먼저 가져가면, 남은 4개 T(4)=False =>철수가 이긴다. T(7) = 1을 먼저 가져가면 남은 6개 T(6) = True => 영희가 이긴다 2를 먼저 가져가면 남은 5개 T(5) = True => 영희가 이긴다 3을 먼저 가져가면 남은 4개 T(4) = False => 철수가 이긴다. T(8) = 1 + T(7)[True] = False 2 + T(6)[True] = False 3 + T(6)[True] = False 8개면 철수는 무조건 진다.
: 그러면 가만 보니 너무 간단하게도 철수는 0,4,8.. 즉, 4n-1의 경우에 지는 것을 알 수 있다. 따라서, 점화식은 T(i) = not (T(i-1) and T(i-2) and T(i-3)) 이런식으로 짜볼 수 있을 것 같다. 즉, 앞에 3개의 케이스에 하나라도 False가 있으면 철수가 이기는 것이다.
코드 및 마무리
: 점화식은 위와 같지만, 사실 코드로 짜면 훨씬 간단해진다. 단지, n을 4로 나눴을 때 철수가 지는 것이기에 이렇게 짜주면 간단하다.
n = int(input())
if n % 4 == 0:
print("NO")
else:
print("YES")
: 동적 계획법은 분할정복법과 비슷하지만, 분할정복법은 위에서 아래(Top to Bottom)이고 동적계획법은 그 반대라는 측면에서 다르다. 그리고 사실 동적계획법이라는 것도 에라토스테네스의 체처럼 어떤 문제해결의 스킬(외워둬야할)이 아닌 일종의 방법론과 같은 것이기에 여러 유형의 문제를 풀어보면서 '접근법'으로써 활용하면 될 것 같다.
