BOJ 2602 (돌다리 건너기)
규칙이 명확하게 보여서 달려들었는데, 생각보다 오래 걸린 문제였다.
이런 DP 문제는 경우의 수를 그려봄과 동시에, 메모용 배열에 어떤식으로 값이 저장되는지를 직접 써보면서 시뮬레이션 해보는게 중요한 것 같다. 이것도 이전 같았으면 분명히 포기했을 문제인데 결국 내 힘으로 풀어내서 기쁘다 ㅠㅠ
접근 방법이 매우 지저분하여 쓰기 민망하지만, 우선은 정리해보려고 한다.
틀렸는데 어디서 틀렸는지 모르겠어요!
KOI 기출 문제는 좀 더 효과적으로 틀린 Case를 확인하는 방법이 있다.
JUNGOL 사이트에서는 채점 결과에서 어느 케이스를 틀렸는지 보여주고 있고, KOI 기출 문제를 대량 보유하고 있기 때문에 백준에 있는 KOI문제라면 어지간해서 이쪽 사이트에도 있다. (다 있을 것 같긴 한데 잘 모르겠음)
내가 잘 풀었는데도 불구하고 틀린 문제가 있다면 여기다 제출해보고 케이스를 확인합시다.
접근한 방법
3차원 배열을 만들어서 메모이제이션을 하는 분들도 많았는데, 개인적으로는 조금 헷갈려서 2차원 배열을 두개 만들어서 했다.
DP[2][완성해야되는 글자수][바닥에 깔린 전체 글자수]
3차원 배열이면 이런 식으로 해서 0, 1에 각각 악마/천사에서 시작한 경우의 수 넣어주면 되고..
2차원 배열로 한다면 D[완성해야되는 글자수][바닥에 깔린 전체 글자수], A[완성해야되는 글자수][바닥에 깔린 전체 글자수] 이런식으로!
배열을 선언할 때 나같은 경우는 글자수만큼 공간을 잡은 것이 아니라 글자수+1만큼 공간을 잡았다. 따라서 아래의 설명은 0번째 칸이 항상 비어있고, 1번째 칸부터 채워넣는 것을 원칙으로 한다.
우선 첫 글자수에 대한 경우의 수를 채워넣어보자. 내가 세운 식은 다음과 같다.
D[i][j] = D[i][j-1] (j에 있는 글자가 현재 채워야할 i번째 글자랑 일치하지 않는 경우)
D[i][j] = D[i][j-1] + D[i-1][j-1] (j에 있는 글자가 현재 채워야할 i번째 글자랑 일치하는 경우)
RGS
RRRGRS
GRGGGS
| D(1)(1) | D(1)(2) | D(1)(3) | D(1)(4) | D(1)(5) | D(1)(6) |
|---|---|---|---|---|---|
| 1 | 2 | 3 | 3 | - | - |
신경써주면 좋은 점이 하나 있는데, 이번에 채워넣어야 하는 글자에 대해 검사할 범위(range)를 정해주면 굳이 끝까지 반복문을 돌려줄 필요가 없다.
내가 채워야하는 글자수가 3이고, 바닥에 깔린 글자는 6자라고 하자. 그러면 첫번째 글자가 채워질 수 있는 경우는 4번째칸까지만 가능하다. (뒤에 5,6번째는 두번째 글자랑 세번째 글자가 채워져야 성립이 되니까)
그러니 굳이 5,6은 검사하지 않고, 1부터 4까지만 검사해서 채우면 되는 것이다. 두번째 글자도 마찬가지다. 두번째 글자에 해당하는 범위인 2부터 5까지만 검사! (두번째 글자 채우려면 앞에는 첫번째 글자가 꼭 와야되니까 1은 제외하는 식으로)
그래서 첫번째 글자에 대한 배열은 D[1][4]까지만 채웠다. 이 범위 내에서 첫번째 글자인 R이 3개 있으므로 D[1][4]는 3이다. 이제 두번째 글자를 채워보자.
| D(1)(1) | D(1)(2) | D(1)(3) | D(1)(4) | D(1)(5) | D(1)(6) |
|---|---|---|---|---|---|
| 1 | 2 | 3 | 3 | - | - |
| D(2)(1) | D(2)(2) | D(2)(3) | D(2)(4) | D(2)(5) | D(2)(6) |
| - | 0 | 2 | 5 | 8 | - |
D[2][2] : 두번째 칸에 채워야할 글자 (G)가 들어있지 않아서 규칙에 맞는 경우의 수가 없음. 이전 칸인 D[2][1]에 있는 값인 0을 땡겨와서 0이 채워짐.
D[2][3] : 세번째 칸에 채워야할 글자 (G)가 들어있어서 규칙에 맞음. 이전 칸인 D[2][2]의 값과, 이전 칸에서 첫번째 글자까지 채운 경우의 수인 D[1][2]를 더해서 2가 채워짐.
D[2][4] : 네번째 칸에 채워야할 글자 (G)가 들어있어서 규칙에 맞음. 이전 칸인 D[2][3]의 값인 2와, 이전 칸에서 첫번째 글자까지 채운 경우의 수인 D[1][3]을 더해서 5가 채워짐.
D[2][5] : 다섯번째 칸에 채워야할 글자 (G)가 들어있어서 규칙에 맞음. 이전 칸인 D[2][4]의 값인 5와, 이전 칸에서 첫번째 글자까지 채운 경우의 수인 D[1][4]을 더해서 8이 채워짐.
D[2][6] : 여기에 두번째 글자를 채우면 세번째 글자는 올 수 있는 자리가 없기 때문에 검사하지 않음.
이런식으로 배열을 끝까지 채워나간 뒤 검사를 하고, 경우의 수를 출력하면 된다.
주의할 점이 있는데, 글자수를 채울 수 없는 경우 0을 출력해야된다는 것.
그런데 어차피 채울 수 없는 경우는, D[완성해야되는 글자수][바닥에 깔린 전체 글자수] 에 0이 들어가게 된다. 그래서 그냥 출력하면 된다..
전체 코드는 링크 참고.