10844_쉬운 계단 수
링크
https://www.acmicpc.net/problem/10844
풀이
잠깐 생각해보면, n-1까지의 계단 수에 어떤 걸 더해서 n까지의 계단 수의 경우의 수를 구할 수 있을 것 같지만 조건이 부족합니다.
계단 수는 마지막 자리의 숫자로 그 다음 자리의 숫자가 뭐가 될지 결정됩니다.
다음 자리의 숫자가 3이 되려면 -1과 +1인 2, 4가 마지막 숫자여야 됩니다.
보통 이렇게 2가지를 갖지만 0과 9는 각각 1과 8가 마지막 자리일 때 가지게 됩니다.
이러한 특성 때문에 계단 수의 경우의 수를 구하기 위해서는 마지막 자리의 어떤 숫자가 몇 개씩 있는지 알아야만 합니다.
n은 1 <= n <= 100이니 101짜리 배열을 만들어야 하고 마지막 자리(0~9)까지 저장해줘야 되기 때문에 DP[101][10]를 만들 수 있겠네요.
맨 처음에는 DP[1][1] ~ DP[1][9]를 1로 초기화 해줍니다. 0으로 시작하는 숫자는 없다고 했기 때문입니다. 1로 초기화를 해줬다면 i=2부터 동적으로 경우의 수를 구할 수 있습니다.
i는 2부터 n까지, j는 0부터 9까지 for문을 돌려줍니다.
j가 0이라면, DP[i][j] = DP[i-1][j+1] 1에서만 올 수 있음.
j가 9라면, DP[i][j] = DP[i-1][j-1] 8에서만 올 수 있음.
다른 경우라면(else), DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1] 양쪽에서 올 수 있음.
다 구한 후 DP[n][0] ~ DP[n][9]를 모두 더하면 총 경우의 수가 나옵니다.
주의할 점은 1,000,000,000으로 나눈 나머지로 출력해야 한다는 것입니다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
//10844_쉬운 계단 수 #include <iostream> #define mod 1000000000 using namespace std;
int DP[101][10];
int main() { int n; int i, j; long long sum = 0;
for (i = 1; i <= 9; ++i) { //1일 때 초기화 -> 2부터 동적으로 구할 수 있음 DP[1][i] = 1; }
cin >> n;
for (i = 2; i <= n; ++i) { for (j = 0; j <= 9; ++j) { if (j == 0) DP[i][j] = DP[i - 1][j + 1]; //1에서만 올 수 있음 else if (j == 9) DP[i][j] = DP[i - 1][j - 1]; //8에서만 올 수 있음 else DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % mod; //양쪽에서 올 수 있음 } }
for (i = 0; i <= 9; ++i) sum += DP[n][i]; //총 경우의 수
cout << sum % mod << endl;
return 0; } |
'PS > BOJ' 카테고리의 다른 글
[백준 BOJ][DP] 2294 동전 2 (3) | 2018.06.02 |
---|---|
[백준 BOJ][DP] 2293 동전 1 (0) | 2018.06.02 |
[백준 BOJ][DP] 1932 정수 삼각형 (0) | 2018.06.01 |
[백준 BOJ][DP] 9095 1, 2, 3 더하기 (0) | 2018.05.27 |
[백준 BOJ][DP] 11727 2xn 타일링 2 (5) | 2018.05.27 |