반응형
https://www.acmicpc.net/problem/1562
1562번: 계단 수
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
[ 문제풀이 ]
https://rudalsd.tistory.com/9?category=1064612
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [ 문제풀이 ] 항상 dp문제를 풀 때는 표를 그려서 어떤 점화식을..
rudalsd.tistory.com
위의 문제와 많이 유사하지만 0~9까지의 모든 숫자가 들어가야 하므로 조금 더 까다로운 문제입니다.
위의 일반적인 계단 수를 구하는 문제를 풀어보시고 오는 것을 추천드립니다!!
쉬운 계단 수 문제와 유사하지만 한가지 개념만 더한다면 쉽게 풀 수 있는 문제입니다.
0~9까지의 모든 숫자가 들어가 있는 계단수는 0과 9에 모두 맞닿아있어야 합니다. 따라서 0에 맞닿아있으면 1번 비트에 저장하고, 9에 맞닿아있으면 2번 비트에 저장하고, 0과 9에 모두 닿아있으면 3번 비트에 저장합니다.
dp배열에 저장해 나가면 결국 3번 비트에 저장돼있는 모든 수를 더하면 정답을 구할 수 있습니다.
[ 소스 코드 ]
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 40 41 42 43 44 45 | #include <iostream> using namespace std; int N; long long dp[10][101][4]; //각 숫자가 들어갈 수 있는 개수를 저장할 배열 //1 : 0과 닿음, 2 : 9와 닿음, 3 : 0, 9와 닿음 int main() { cin >> N; long long cnt = 0; //총 개수를 저장할 변수 for (int i = 1; i < 9; i++) { //N이 1일 때 0을 제외한 각 숫자가 한번씩 들어갈 수 있으므로 dp[i][1][0] = 1; //모두 1로 경신 } dp[9][1][2] = 1; for (int i = 2; i <= N; i++) { //2자릿수 부터 돌면서 for (int j = 0; j < 10; j++) { for (int k = 0; k < 4; k++) { if (j == 0) { //0과 닿아있으면 k|1에 그 전의 모든 값들을 더함 dp[j][i][k | 1] += dp[1][i - 1][k]; dp[j][i][k | 1] %= 1000000000; } else if (j == 9) { //9와 닿아있으면 k|2에 그 전의 모든 값들을 더함 dp[j][i][k | 2] += dp[8][i - 1][k]; dp[j][i][k | 2] %= 1000000000; } else { //아니라면 전의 값들 중 계단수들의 값들을 더함 dp[j][i][k] = dp[j - 1][i - 1][k] + dp[j + 1][i - 1][k]; dp[j][i][k] %= 1000000000; } } } } for (int i = 0; i < 10; i++) { cnt += dp[i][N][3]; cnt %= 1000000000; } cout << cnt; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1149번 - RGB거리 (C++) (0) | 2022.05.31 |
|---|---|
| [ 백준 ] 1799번 - 비숍 (C++) (0) | 2022.05.30 |
| [ 백준 ] 10844번 - 쉬운 계단 수 (C++) (0) | 2022.05.28 |
| [ 백준 ] 2407번 - 조합 (C++) (0) | 2022.05.27 |
| [ 백준 ] 1509번 - 팰린드롬 분할 (C++) (0) | 2022.05.26 |