[백준][dp] 10844 쉬운 계단 수 c++ 구현

목차

 

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

10844번: 쉬운 계단 수

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 구현 방향

다이나믹 프로그래밍의 방법 중 하나인 상향식을 이용해 구현하고자 했다.

다이나믹 프로그래밍의 개념을 모른다면 아래 링크를 참고하면 좋다

https://be-senior-developer.tistory.com/19

[DP] 동적 계획법 알고리즘 c++ 설명

 

 

 

 

문제 풀이 시 주의점

매우 큰 수를 저장해야 하기 때문에 %연산자를 잘 활용해야 하는 문제이다.

또한 배열에 넣어서 푸는 방식으로 하면 너무 많은 수를 저장해야 되기 때문에 오류에 빠진다..

 

잘못된 코드 구현

#include<iostream>
#include<vector>
#include<algorithm>
#include <cmath>
using namespace std;

vector<int>stair[100000];



int main() {

int n, i, j, lastnum;
long long int ans = 1000000000;
cin >> n;
for (i = 0; i < 9; i++) {
    stair[0].push_back(i+1);    
}

for (i = 1; i < n; i++) {
    for (j = 0; j < stair[i-1].size(); j++) {
        lastnum = stair[i-1][j] / pow(10, i - 1);

        if (lastnum == 9) {   //마지막 자리가 9일때
            stair[i].push_back(stair[i-1][j] * 10 + lastnum - 1);
        }
        else {   
            stair[i].push_back(stair[i-1][j] * 10 + lastnum-1);
            stair[i].push_back(stair[i-1][j] * 10 + lastnum+1);
        }
    }
}

cout << stair[n - 1].size();     //크기를 구해준다.

}

 

 

문제 풀이

마지막 자리만 잘 고려해주면 점화식을 만들 수 있는 문제였다

0~9까지의 숫자를 배열로 만들어 세어주는 식으로 풀면 된다.

 

 

길이가 1인 계단일 때 0~9까지의 개수

0

1

1

1

1

1

1

1

1

1

 

 

 

길이가 2인 계단일 때 0~9까지의 개수

1

1

2

2

2

2

2

2

2

1

 

 

 

길이가 3인 계단일 때 0~9까지의 개수

1

3

3

4

4

4

4

4

3

2

 

 

케이스를 총 3가지 경우로 나누어주면 된다.

 

• 0의 개수 (j =0)

그 전 길이 계단의 j+1의 개수이다.

 

 

• 9의 개수 (j =9)

그 전 길이 계단의 j-1의 개수이다.

 

 

• 그 외 (j = 1~8)

그 전 길이 계단의 j-1과 j+1의 합이다.

 

 

 

 

코드 구현

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<long long int>stair_size[10000];

int main() {
    
    int n, i, j;
    long long int mod = 1000000000, stair=0;     
    cin >> n;
   //처음은 0 1 1 1 1 1 1 1 1 1 로 초기화 해준다.
    for (i = 0; i <= 9; i++) {
        stair_size[0].push_back(1);
    }

    stair_size[0][0] = 0;  

    for (i = 1; i < n; i++) {
        stair_size[i].resize(10, 0);   //배열 초기화
        for (j = 0; j <= 9; j++) {
            if (j == 0) {    
                stair_size[i][j] = stair_size[i-1][j+1]%mod;   
                
            }
            else if (j == 9) {
                stair_size[i][j] = stair_size[i-1][j-1]%mod;

            }
            else {
                stair_size[i][j] = stair_size[i-1][j-1]%mod + stair_size[i - 1][j+1] % mod;
            }
        }
    }

      for (i = 0; i <= 9; i++) {
            stair += stair_size[n - 1][i];   //각 개수를 다 더해준다.
      }

     cout << stair%mod;   


}

 

dp는 아직도 어렵다..