[백준/C++] 10844번 - DP (설명 포함)

문제 접근 

일단 주어진 테스트 케이스에 맞춰서 상황을 살펴봤다.

N = 1)
1 / 2/ 3/ 4/ 5/ 6/ 7/ 8/ 9

N = 2)
10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98 
0 - 1
1 - 0,2
2 - 1,3
3 - 2,4
4 - 3,5
5 - 4,6
6 - 5,7
7 - 6,8
8 - 7,9
9 - 8

N = 3)
101 
123 121 
234 232 
212 210
321 323
...

 

보면 자기 자신에 +1,-1 한 숫자들 만큼이 인접한 숫자가 된다.

그래서 0이나 9일 떄는 1개씩밖에 못 더해준다. (0일 떄는 -1을 못하고, 9일 떄는 +1을 못하기 떄문)

보면 N=2일 때의 값은, N=1인 숫자들에 +2 씩 해주고, 9일 때만 +1 해주면 된다.

 

N이 몇자리 수 이든간에, 가장 오른쪽에 있는 숫자에 맞춰서 +1,-1을 해주면된다.

N-1 자리 수까지는 다 연속된 수로 구성되어 있다고 생각하고 진행할 것이기 떄문이다.

 

---

일반화

d[i][j] += d[i-1][j-1] + d[i-1][j+1];

 

 

i는 N자리수를 의미한다고 보면 된다. 

j는 0~9까지이고, 위의 일반화 식에는 중요한 조건이 있다.

 

j가 0이라면 d[i-1][j-1]을 더해주면 안되고, (0에서 하나 더 작은 수는 -1로 음수가 되므로)

j가 9라면 d[i-1][j+1]을 더해주면 안된다. (9에서 하나 더 큰 수는 10으로 한자리수 가 아니므로)

 

 

초기조건

d[1][1] ~ d[1][9] = 1 로 초기 설정을 해주면 된다.

 

예시

• d[2][3] += d[1][3+1] + d[1][3-1];

2자리 자연수 중에서 계단 수를 찾는 것이다.

그 중에서 j=3이니까, 3으로 시작하는 두자리 자연수 중 계단 수의 개수를 찾는 항이라고 보면 된다.

3의 옆에는 4나 2가 올 수 있고, N이 2인 상태에서는 N-1=1의 상태를 참고해 나갈 것이므로

N이 1일 때 4와 2의 계단 수 개수를 더해주면 된다.

(34 = 1개) + (32 = 1개) = 2개

 

• d[3][3] += d[2][3+1] + d[2][3-1]

하나 더 봐보자. 3자리 자연수 중에서 3으로 시작하는 계단 수를 찾고 싶다.

그리고 2자리 자연수 중 3과 연속된 숫자인 4와 2로 시작하는 계단수를 이용해서 찾아가려고 한다.

이미 반복문을 통해서 d[2][j]가 다 완성되어 있을테니 바로 계산이 가능해진다.

 

한 마디로, 3으로 시작하는 계단수를 찾기 위해서, 3의 양 옆 연속된 숫자들의 계단수로 쪼개서 찾아가는 거다.

1. 3으로 시작하는 계단 수 찾을래 
2. 34_ OR 32_ 이런 상황이네.
3. 그러면 일단 4_ 와 2_를 해결하자. 어 그러면 N=2인 4의 계단수 찾는게 되네? (d[2][4]와 d[2][2] 찾는 문제로 작아짐)
  3-1. 4다음에는 5나 3일 올 수 있네. 어 그러면 한 번 더 쪼개서 N=1인 5와 3의 계단수를 찾으면 d[2][4]=2가 되네
  3-2. 2다음에는 1이나 3이 올 수 있네. 어 그러면 한 번 더 쪼개서 N=1인 1과 3의 계단수를 찾아 더하면 d[2][2] =2 가 되네
4. 자 그러면 다시 3번으로 돌아가면 4_ 와 2_로 시작하는 계단 수는 4개가되고
    2번의 문제도 해결한 상태가 되네? 답은 4개!

 

>> 345 - 343 - 323 - 321

 

구현

#include <bits/stdc++.h>
using namespace std;

int n;
long long d[101][10];
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    //d[i][j] = i 자리 수 일 때, j의 인접 수 개수 
    cin >> n;
    
    //초기화
    for (int i=1;i<=9;++i){
        d[1][i]=1;
    }

    for(int i=2;i<=n;++i){
        for (int k=0;k<=9;++k){
            if (k!=0) d[i][k] += d[i-1][k-1];
            if (k!=9) d[i][k] += d[i-1][k+1];
            d[i][k]%=1000000000;
        }
    }

    long long ans = 0;
    for (int i=0;i<=9;++i){
        ans+=d[n][i];
    }
    ans%=1000000000;
    cout<<ans;
}

 

 

dp는 점화식을 세우는게 어렵다.

적당히 1차원 배열도 쓰고, 2차원 배열도 같이 써야하는 것 같ㄷ..r