[모각코] DP 2

1. 돌 게임2

https://www.acmicpc.net/problem/9656

첫 번째로 풀어볼 문제는 돌 게임 2이다.

돌 N개를 상근이와 창영이 둘이서 1개 또는 3개씩 가져가며, 마지막에 돌을 가져간 사람이 진다. 규칙을 찾아야 하기 때문에 돌의 개수가 1인 경우부터 따져보자.

돌이 1개 있는 경우 턴은 상근이부터 시작하므로 상근이가 돌을 가져가 창영이가 이긴다.(CY)

돌이 2개 있는 경우 상근이가 1개, 창영이가 1개 가져가 상근이가 이긴다.(SK)

돌이 3개 있는 경우 상근이가 3개를 가져가면 패배이므로 1개를 가져가고, 창영이가 1개, 다시 상근이가 1개 가져가 창영이가 이긴다.(CY)

돌이 4개 있는 경우 상근이가 3개, 창영이가 1개를 가져가 상근이가 이기거나, 상근이가 1개, 창영이가 1개, 다시 상근이가 1개, 창영이가 1개 가져가 결국 상근이가 이긴다.(SK)

지금까지를 보면 돌의 개수가 N-1개 이거나 N-3개일 때 진 사람이 승리한다.

따라서 이를 이용해 돌이 5개일 때를 보자.

5개인 상태에서 상근이가 1개를 가져간다. 이 때 N-1, 즉 4개의 돌일 때 패배했던 것은 창영이다. 마저 해보면 창영이가 3개를 가져가고 상근이가 1개를 가져가 창영이가 승리한다. 만약 상근이가 3개를 가져갔다면 창영이는 1개를 가져가 상근이가 마지막 돌을 가져가게 만들어 창영이가 승리한다. 마찬가지로 N-3, 즉 3개일 때 창영이는 패배했다.

이제 이를 이용해 코드를 작성해보자. 위의 규칙을 통해 DP 테이블을 채워나가 마지막 N번째의 승자를 출력하면 된다.

DP 테이블은 4까지 직접 계산해봤으니 5부터 채워나간다.

테이블에 들어갈 값은 상근이가 이기면 s, 창영이가 이기면 c가 입력된다.

2. 설탕 배달

두 번째로 풀어볼 문제는 설탕 배달이다. https://www.acmicpc.net/problem/2839

N킬로그램의 설탕을 3 또는 5킬로그램씩 배달하는데 각각이 아닌 3 또는 5킬로그램 설탕 봉지가 총 몇 봉지인지 구하는 문제이다. 두 종류의 설탕 봉지로 나눌 수 없다면 -1을 출력해야 한다.

사실 이 문제는 이전에 나눗셈으로 풀어본 적이 있다. 하지만 다이나믹 프로그래밍으로는 해결해 본 적이 없기 때문에 이전에 사용했던 나눗셈 방법은 제외하고 생각하였다.

위의 돌 문제와 비슷하게 규칙을 만들어 보면 이 또한 N-3 그리고 N-5인 경우를 생각해보면 된다. N킬로그램을 만들기 위해서는 N-3킬로그램에 3킬로그램 봉지를 추가하거나 N-5킬로그램 봉지에 5킬로그램 봉지를 추가해야 한다. 결국 N킬로그램 이전에 N-3 또는 N-5 킬로그램으로 구성이 가능했는지, 그리고 그것은 몇 봉지였는지를 기억하고 있는 것이 핵심이다. 이는 위 문제처럼 이전의 작은 문제의 결과를 기억했다가 큰 문제를 푸는 데 반복적으로 사용하게 되어 결국 다이나믹 프로그래밍으로 해결할 수 있는 문제라는 것을 알 수 있다.

그렇다면 바로 코드를 작성해 보자.

3. 마무리

다이나믹 프로그래밍 분류로 되어 있는 문제들을 찾아서 푼 것이라 DP를 적용하여 풀 생각을 했지만 단순히 문제와 조건을 보고 DP로 풀어야겠다고 떠올리기는 아직 쉽지 않을 것 같다. 우선 문제와 조건을 보고 테스트케이스들을 하나 둘 세워 먼저 관계를 파악하고 나서 DP를 사용할 수 있는 조건인지를 따지는 습관을 잘 들여야 할 것 같다. 아직 몇 문제 풀어보지 않았지만 이전에 풀었던 것과 다르게 DP로 문제를 풀어봤을 때 오히려 생각한 것이 코드로 좀 더 간결하게 나왔다. 머릿속에서 관계식을 생각하다 보면 정리되지 않고 꼬인 것처럼 코드를 작성하는 경우가 종종 있었는데 확실히 더 좋은 방법을 찾았다는 생각이 든다. 물론 문제를 보고 적용할 수 있는 조건인지를 파악하는 것이 더 우선인 것 같고 앞으로 공부해 나가며 깨닫는 바가 있기를 바란다.