[BaekJoon/백준] 10844번 | 복습 1회 완료

동적계획법 문제.

 

계단수를 찾는 문제다.

 

길이가 N인 숫자에서 계단수를 찾고, 그 결과를 이용해서 길이가 N + 1인 숫자에서의 계단수를 찾는다.

 

최근 문제들은 거의 이렇게 '반복문을 이용한 동적계획법'인 Bottom - up 방식으로 문제를 풀었다. 메모이제이션도 사용됐다고 보면 된다. (엄밀하겐 타뷸레이션이긴한데.. 구분지을 필요는 없을 것 같다. hevton.tistory.com/295)

#include <iostream>
using namespace std;

//a[x][y] x : 길이(0 = 1자리로 계산했음), y : 앞자리를 y로 하는 수의 계단수 개수
long long a[100][10] = { {1,1,1,1,1,1,1,1,1,1}, };
int N;
int main() {
    cin >> N;
    for(int i = 1; i < N ; i++) { // 길이
        
        for(int j = 0; j < 10; j++) { // j로 시작하는 맨 앞 자리 (0 가능) -> 이유 : 그 다음 자리에서 사용하려면 0부터 시작하는 연속된 계단수도 필요해 -> 세자리를 예시로, 110 121 전에 101이라는 0으로 시작하는 두자리의 연속된 계단수가 필요해. j=1부터 하면 세자리에서 101을 얻지 못하고 110부터 시작되는것임)
            for(int k = 0; k < 10; k++) { // k로 시작하는 뒷자리(두번째자리) (0 가능)
                if(abs(j-k) == 1) // 계단수인 경우
                    a[i][j] = (a[i - 1][k] + a[i][j]) % 1000000000;
            }
        }
    }
    long long result = 0;
    for(int i = 1; i <= 9; i++) { // 실제 도출은 0이 아닌 1부터. -> 세자리를 토대로 계산한 예시일 때, 010 012는 다음 네 자리 계산을 위해 넣어놨지만, 실제 세 자리에 속하진 않으므로 1부터 시작해야함.
        result = (a[N - 1][i] + result)%1000000000;
    }
    
    cout << result;
}

 기존 j = 1부터 , 그리고 result는 0 부터는

 

 두자리에서

 10

 12

 를 도출하나.

 세자리부터는

 101 이 없고

 110

 112 이렇게 두개만 도출한다.

 

 또한 result 0부터는

 맨 앞자리가 0인 숫자부터 출력하므로 이건 말이 안된다.

 ex ) 1~9가 아닌 0~9를 출력하는 것.

 ex ) 101부터가 아닌 010 부터 출력하는것

 

 즉, 저렇게 바꾼 이유는

 j = 0부터는 계산을 위한 것. 그러므로 result 는 실제 앞자리 (1부터 시작가능)부터의 실질값을 사용해야함.

 

 

 

---

2021.02.24 복습

다시 풀어보았다. 예전엔 3중 포문으로 구현했더라. 생각해보니 3중으로 할 필요가 없다. 2중이면 충분하다.

#include <stdio.h>

int dp[101][10] = {{0, }, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},}; // 1~100(0은안씀) | 0 ~ 9
int N;
int sum;

int main() {
    
    scanf("%d", &N);
    
    for(int i = 2; i <= N; i++) {
        for(int j = 0; j < 10; j++) {
            
            int a = (j - 1 >= 0)?dp[i - 1][j - 1]:0;
            int b = (j + 1 <= 9)?dp[i - 1][j + 1]:0;
            
            dp[i][j] = (a + b) % 1000000000;
            

        }
    }
    
    // dp[K][0]도 계산해왔지만, 0으로 시작하는 수는 없으므로, 실제 도출 시엔 i = 1부터.
    for(int i = 1; i < 10; i++) {
        sum = (sum +dp[N][i]) % 1000000000;
    }
    
    printf("%d", sum);
}


/*

 1 ~ 9 계단수
 
 12
 21 23
 3
 4
 5
 .
 .
 .
 N 
 
 dp[i][j] = 길이가 i, 시작숫자가 j인 계단수의 개수
 
 
 1 01234 도 존재할수 있다는 점을 주의.
 */