Dynamic Programming 문제는 결국 점화식을 찾는 게 관건이다.
즉 현재 상태가 이전 상태에 어떻게 의존하는지, 어떤 관계 속에 놓여있는지 파악해야 한다.
DP 문제 풀이 접근 방식은 다음과 같다.
1) 머리만 굴리지 말고 직접 손으로 써본다. 어차피 DP는 점화식을 찾는 문제고, 점화식은 곧 이전 항과 현재 항 사이 숨은 패턴을 찾는 일이다. 다행히 직접 반복해보면서 써보면 패턴을 발견하게 되는 경우가 대부분이다.
테스트 케이스나 (테스트 케이스가 적절하지 않다면) 직접 예시를 고안해서 4~5개 항 정도 추론해볼 것.
2) 문제 조건을 결정 짓는 핵심 정보는 무엇인가?
3) 현재 상태가 이전 상태에 어떻게 의존하는가?
4) DP 배열의 정보를 명확히 설정한다. 1차원인가? 2차원 또는 그 이상인가? 각 차원의 크기는?(N인지, N+1인지가 정말 중요하다)
각 차원마다 어떤 정보를 담고 있는가? 최종 배열이 담고 있는 값은 무엇인가?
dp 배열에 대한 설명을 아예 코드 주석에 같이 쓰는 습관을 들이는 게 좋다.
백준 10942번: 팰린드롬?
어떤 수열이 주어졌을 때, S와 E 두 인덱스로 부분수열을 만들어서 팰린드롬(앞뒤 거꾸로 순서를 뒤집어도 같은 문자열)인지 확인하는 문제다.
이 문제에선 편견을 버리는 게 중요하다.
dp 배열을 항상 오름차순으로, 왼쪽에서 오른쪽으로 1차원으로만 업데이트한다는 생각을 버리자.
3) 현재 상태가 이전 상태에 어떻게 의존하는가?
팰린드롬 X(이전 상태)가 존재할 때, 그 문자열을 가운데에 놓고 양옆으로 같은 문자를 계속 붙여서 확장한 문자열(현재 상태)도 팰린드롬이다.
위 관계만 잘 포착하면 문제의 절반은 다 풀린 것이다.
4) dp 배열 정보를 명확히 설정한다.
- dp 배열은 2차원이다.
- dp[n][k] = V 일 때, n번째 문자부터 시작하여 k번째 문자를 포함하는 문자열일 때 팰린드롬이면 V = 1, 아니면 V = 0로 설정한다.
- 길이가 1인 문자열은 모두 팰린드롬이라고 설정해야 양옆에 앞뒤로 같은 문자열을 붙여서 팰린드롬을 만들 때 여전히 팰린드롬이라는 결론이 도출된다.
dp = [[0]*N for _ in range(N)]
for n in range(N):
dp[n][n] = 1
- 처음 확장하기 전 문자열 길이가 1이냐, 또는 2이냐에 따라 경우가 2가지로 나뉜다.
백준 17070번: 파이프 옮기기 1
이 문제는 비교적 점화식이 명확하게 보이는 문제였다.
2) 문제 조건을 결정 짓는 핵심 정보는 무엇인가?
파이프의 이전 위치가
1) 가로로 놓여있는가?
2) 대각선으로 놓여있는가?
3) 세로로 놓여있는가?
에 따라서 현재 이동할 수 있는 칸이 달라진다. 이 정보를 그대로 dp 배열에 반영하면 된다.
4) dp 배열 정보를 명확히 설정한다.
- 파이프의 위치 상태가 총 3가지(가로, 대각선, 세로)이므로 가로면 0, 대각선이면 1, 세로이면 2로 표현할 수 있다.
- 2차원 N*N 크기의 격자판이 주어졌으므로, 각 칸(i, j , 0 <= i < N, 0 <= j < N)에 대해 상태를 저장해놓자.
- 따라서 dp 배열의 총 차원 수는 2차원 격자판의 2 + 위치 상태 3가지를 표현할 수 있는 1차원 1 = 3차원이 된다.
- dp[r][c][i]: r번째 행, c번째 열의 칸에서 파이프가 가로(i=0), 대각선(i=1), 세로(i=2)로 놓여있는 경우의 가짓수이다.
dp = [ [[0]*3 for _ in range(N)] for _ in range(N)]
dp[0][1][0] = 1
dp 배열을 업데이트하기 위해서는 초기 조건을 설정하는 게 중요하다.
이 문제에선 (0,1) 번째 칸에 파이프가 가로로 놓여있는 데서 출발한다고 했으므로 dp[0][1][0] = 1 로 설정해주었다.
