다이나믹 프로그래밍 - 여러번 주사위 굴려서 정해진 숫자 맞추기
f면 주사위 d개를 굴려 합이 target이 되는 경우의 수를 구하는 DP 문제. 브루트포스에서 출발해 중복 sub-problem을 찾아 동적 프로그래밍으로 접근하는 과정을 상태 공간 트리와 함께 정리합니다.
Number of Dice Rolls With Target Sum
이번에도 Leetcode에서 발췌한 문제이다. 동적 프로그래밍으로 풀어야 하는데 쉬운 문제는 동적 프로그래밍임을 알고 나면 쉽게 풀린 적이 많았다. 하지만 이 문제는 알고 나서도 답을 보고 나서도 쉽게 이해가지가 않았던 문제이다. 동적 프로그래밍인 만큼 반복되는 sub-problem을 찾아야 하는데 이것을 찾는 개념을 잡는 게 힘들었던 것 같다. 이번에 글로 정리하면서 조금이나마 뇌에 각인이 되었으면 좋겠다.
여담으로 Learn how to learn에서 바바라 교수님이 말했듯이, 뇌는 한번 생각했던 것을 반복해서 생각한다고 한다. 즉 잘못된 접근 방법을 처음에 떠올렸다면 다시 풀때도 잘못된 방법을 먼저 떠올린다는 것이다. 그래서 다른 생각을 떠올리려면 근육을 키우듯 뇌에 새겨진 패턴을 반복적인 잡을 통해 바꿔야 한다고 한다. 반복, 연습 이것만이 다이나믹 프로그래밍을 푸는 핵심이 아닐까 생각한다. 결론은 노가다...AI도 노가다니까 뭐 fair enough.
문제 설명
우리에게 f면을 가진 주사위가 d개 만큼 주어진다. f면은 1,2, .... ,f 이다. 이때 주사위를 굴린 합이 target (목푯 값)이 될 수 있는 모든 경우의 수를 모듈러 10^9 + 7을 해서 구하라. 참고 경우의 수를 10^9+7로 나눈 후 값을 리턴하면 된다.
그리고 총 경우의 수는 f^d이다.
예제 1:
Input: d = 1, f = 6, target = 3
Output: 1
설명: 6면으로 된 한 개의 주사위를 던졌을 때 합이 3이 될 수 있는 경우의 수는 1개이다.
예제 2:
Input: d = 2, f = 6, target = 7
Output: 6
설명: 6면으로 된 주사위 2개를 던져서 합이 7이되는 경우의 수는 6이다. (1+6, 2+5, 3+4, 4+3, 5+2, 6+1)
예제 3:
Input: d = 2, f = 5, target = 10
Output: 1
설명: 5면으로 된 주사위 2개를 던져서 합이 10이 되는 경우의 수는 오직 한 개뿐이다. (5+5)
예제 4:
Input: d = 1, f = 2, target = 3
Output: 0
설명: 2면으로 된 주사위 한개를 던져서 합이 3이 되는 것은 불가능하다. 따라서 경우의 수는 없다.
예제 5:
Input: d = 30, f = 30, target = 500
Output: 222616187
설명: 자세한 설명은 생략한다. 경우의 수가 매우 크기 때문에 10^9 + 7의 나머지를 리턴하지 않으면 오답이 될 것이다.
제약조건:
1 <= d <=30 그리고 1 <= target <= 1000
Thought Process
예제가 많은 것이 심상치 않다. 그만큼 경우의 수가 다양하기 때문에 최대한 많은 케이스를 설명하려고 하기 때문에 예제가 많은 게 아닐까 개인적으로 생각해 보았다. 일단 모든 경우의 수를 보면 나이브한 브루트 포스(무차별 공격)적인 방법으로 계산을 하면 시간 복잡도가 지수만큼 커진다는 것을 알 수 있다. 그것도 면이 많고 주사위가 많으면 많을수록 비약적으로 늘어나기 때문에 원하는 답이 아니라는 것을 알 수 있다.
그럼에도 불구하고, 브루트포스로 접근하는 것은 생각보다 좋은 시작이 될 수 있다. 경우의 수를 구하는 대부분이 그렇듯이 재귀적인 방법으로 푸는 것이 일반적이다. 그리고 재귀적인 방법으로 푼 것을 따라가 보면 반복되는 포인트를 찾을 수 있다. 방법은 여러 가지가 있겠지만 일반적으로 재귀 상태를 잘 표현하는 것은 상태 공간 트리(State-Space Tree)를 사용하는 것이다.
개념적인 트리로써 자료구조와는 상관이 없다. 어쨌거나 저런 식으로 중간 상태를 노드로 표현을 하면 중복해서 계산하는 부분이 눈이 잘 들어 올 것이다.
패턴 찾기
이번 문제도 마찬가지로 중복되는 계산을 찾는 것이 중요하다.
예를 들자면 주사위 3개가 있다고 생각해보자. 그리고 목표 값은 7이다.
한 개의 주사위 값이 1이면, 주사위 2개가 7-1=6 이 되는 경우의 수를 찾아야 한다.
한 개의 주사위 값이 2이면, 주사위 2개가 7-2=5 가 되는 경우의 수를 찾아야 한다.
...
위와 같은 패턴을 발견했다면 어느 정도 진도가 나간 것이다. 위와 같은 패턴을 발견하고 코드로 옮기는 것은 또 다른 어려움이 있다.
글이 길어져서 2편으로 나누어 정리하도록 하겠다.