반응형
https://www.acmicpc.net/problem/10844
10844번: 쉬운 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
[ 문제풀이 ]
항상 dp문제를 풀 때는 표를 그려서 어떤 점화식을 세우면 될지 생각해보면 쉽게 답이 나오는 경우가 많았습니다.
이번에도 먼저 10X100 배열을 만들어서 값들을 넣어 보았고 바로 점화식이 떠올라 쉽게 답을 구할 수 있었습니다.
일단 첫째자리에 올 수 있는 숫자는 0을 제외한 1~9까지의 수이므로 9개입니다. 이를 표로 표현하면 다음과 같습니다.
그 후 두번째 자리에 올 수 있는 수들은 첫 번째 자리에 오는 수와 값이 1이 차이가 나면 되므로 앞의 수가 지금의 수와 절댓값이 1 차이가 나면 됩니다. 따라서 dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + dp[ i - 1 ][ j + 1 ]이 됩니다. 하지만 0과 9는 각각 1과 8만 올 수 있으므로 예외 처리해주면 됩니다.
마지막으로 N번째 열의 값들을 모두 더해주면 N의 자리수의 계단수들을 모두 구할 수 있습니다.
하지만 구하고자하는 값이 int형 범위를 넘어서는 값들이고 문제의 조건에서 1,000,000,000으로 나눈 나머지 값을 출력하라고 했으므로 모든 연산이 끝나고 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 33 34 35 36 37 38 39 | #include <iostream> using namespace std; int N; long long dp[10][101]; //각 숫자가 들어갈 수 있는 개수를 저장할 배열 int main() { cin >> N; long long cnt = 0; //총 개수를 저장할 변수 for (int i = 1; i < 10; i++) { //N이 1일 때 0을 제외한 각 숫자가 한번씩 들어갈 수 있으므로 dp[i][1] = 1; //모두 1로 경신 } for (int i = 2; i <= N; i++) { //2자릿수 부터 돌면서 for (int j = 0; j < 10; j++) { if (j == 0) { //0일 때는 1밖에 올 수 없으므로 dp[j][i] = dp[1][i - 1]; } else if (j == 9) { //9일 때는 8밖에 올 수 없으므로 dp[j][i] = dp[8][i - 1]; } else { //값이 1차이나는 수들의 값을 모두 더해줌 dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1]; } dp[j][i] %= 1000000000; //더해준 값을 1000000000으로 나눈 나머지로 경신 } } for (int i = 0; i < 10; i++) { cnt += dp[i][N]; //각 숫자마다 올 수 있는 숫자들을 더하고 cnt %= 1000000000; //1000000000으로 나눈 나머지로 경신해준다. } cout << cnt; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1799번 - 비숍 (C++) (0) | 2022.05.30 |
|---|---|
| [ 백준 ] 1562번 - 계단 수 (C++) (0) | 2022.05.29 |
| [ 백준 ] 2407번 - 조합 (C++) (0) | 2022.05.27 |
| [ 백준 ] 1509번 - 팰린드롬 분할 (C++) (0) | 2022.05.26 |
| [ 백준 ] 1208번 - 부분수열의 합 2 (C++) (0) | 2022.05.25 |