백준, BOJ, 10844번 C++ [CPP]

하.. 이건 방법은 알았지만

구현이 잘못되어서 시간이 오래걸렸다.

 

https://www.acmicpc.net/problem/10844

 

---

 

#맞는 풀이

#include<iostream>
#define X 1000000000

using namespace std;


int N;
long long dp[101][10];


int main(){
    cin >> N;
    dp[1][0] = 0;
    for(int i = 1; i<=9; i++){
        dp[1][i] = 1;
    }
    
    for(int i = 2; i<=N; i++){
        for(int j = 1; j<=8; j++){
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%X;
        }
        dp[i][0] = (dp[i-1][1])%X;
        dp[i][9] = (dp[i-1][8])%X;
    }
    
    long long sum = 0;
    for(int i=0; i<=9; i++){
        sum += dp[N][i];
    }
    
    cout << sum%X ;
}

 

우선 크기가 큰 걸로보아 long long 쓰는 것이 맞는 것으로 보인다.

 

길이가 1인 처음 것을 보자.

0은 못들어가고

1,2,3,4,5,6,7,8,9

9개 있다.

---

길이가 2인 두번째 것을 보자.

0은 못들어가고

1,2,3,4,5,6,7,8,9가 들어갈 수 있다.

그 뒤에는 1이선택되면 0,2 

2가 선택되면 1,3

...

9가 선택되면 8

총 17개다.

---

길이가 3이면..?

0은 못들어가고 

1~9가 들어간다.

그 다음 자리는

1이면 0,2

....

9면 8이 들어간다.

다음 자리는

0이면 1...

...

9면 8 이 들어간다.

 

---

 

다시 말하면

이렇게 퍼져나간다.

3번 째 자리

1  -> (0,2) ->  0이면 (1)  2면(1,3) 

다시 말해서 세번 째 자리에 1이 들어가면 두 번째 자리에서의 0과 2로 만들어질 수 있는 가짓수가 들어가고

두번 째 자리에서 0과 2로 만들어질 수 있는 가짓 수는 첫번 째 자리에서의 1번과 또 1번과 3번이다. 

즉, 3가지다.

 

다시 말하면

세번째 자리를 선택을 한다면 2번째 자리의 수에서 뽑혀진 (최대)2개의 가짓 수를 더하면 되는 거싱고

2개의 가짓수는 1번 째 자리의 수에서 뽑혀진 (최대)4개의 가짓수를 더하면 된다.

다만 0이 뽑히거나 9가 뽑혔을 때는 예외처리를 해주면 된다.

 

말로는 쉬운데.. 구현이 은근 헷갈린다.

 

나중에 다시 풀어보도록 하자

 

---

사실 위에 식은 우연히 생각한 식이 맞은 것이다.

원리는 비슷하지만 조금 달랐다.

 

맨 앞자리 숫자는 1~9밖에 못온다.

하지만 위의 식에서는 0번째 항까지 더했다.

그래서 답이 나왔다.

조금 뭐가 이상하지 않나??

 

N자리일 때

1이 선택됐을 때 N-1이 올 수 있는 계단수

...

9가 선택 ...

이렇게 9까지 구하면 되겠다.

 

하지만0, 1, 9에 대해서는 예외가 발생한다.

 

그래서 다음과 같이 짜야한다.

#include<iostream>
#define X 1000000000

using namespace std;


int N;
int dp[10][101];

//start로 시작하는 number자리에서의 가짓 수
int stair(int start, int number){
    //base condition
    if(number == 1) return 1;
    
    //이미 계산되어 있다면 바로 return
    int& ret = dp[start][number];  // -> 이 표현 중요
    //dp[start][number]의 주소가 ret에 할당됨.
    //즉 ret가 dp[start][number]를 가리키게 됨.
    //ret에 할당된 값이 있다면 그 값을 반환.
    if(ret) return ret;
    
    //계산되어있지 않으면
    ret = 0;
    if(start == 0){
        ret += stair(1,number-1);
        ret %= X;
    }else if(start == 9){
        ret += stair(8,number-1);
        ret %= X;
    }
    else{
        ret += stair(start-1,number-1) + stair(start+1, number-1);
        ret %= X;
    }
    
    return ret;
    

}

int main(){
    cin >> N;

    int sum = 0;
    for(int i = 1; i<=9; i++){
        sum += stair(i, N);
        sum %= X;
    }
    
    cout << sum;
}