-
백준 알고리즘, 10844 문제Algorithms/ACM_ICPC 2018. 7. 23. 01:45
풀이
2 자리수 부터 생각해보면 다음과 같다.
1 --> 0, 2
2 --> 1, 3
3 --> 2, 4
...
9 --> 8
3 자리수는 다음과 같다.
0 --> 1
1 --> 0, 1
...
8 --> 7, 9
9 --> 8
이렇게 살펴보면, 3 자리수 부터 다음의 규칙이 적용된다는 것을 알 수 있다.
1. 0 이 나오면 다음 수는 1 이 와야한다.
2. 9 가 나오면 다음 수는 8 이 와야한다.
3. 1 ~ 8 의 다음 수는 각각 2개가 있다.
이 규칙을 그림으로 그려보면, 점화식을 생각해 낼 수 있을 것 이다.
위 표에서 열은 해당 자리수의 마지막 수를 나타낸다.
그리고 값의 자리는 해당 자리수의 각각의 마지막 수가 나오는 경우의 수다.
그렇다면 이제 위 표를 DP 배열로 나타내고 입력받은 N 자리수에 대한 해당 열의 모든 수를 더해주면
우리가 구하고자 하는 값이 나올 것이다.
이제 점화식을 만들 차례다.
0 , 1 ~ 8, 9 에 따라 다른 값이 적용되어야 하므로
1. 어떤 자리수 n 의 마지막 숫자가 0 이면
DP[n][j == 0] = DP[n - 1][1];
2. 어떤 자리수 n 의 마지막 숫자가 1 ~ 8 이면
DP[n][j == 1...8] = DP[n - 1][j - 1] + DP[n - 1][j + 1];
3. 어떤 자리수 n 의 마지막 숫자가 9 이면
DP[n][j == 9] = DP[n - 1][8];
코드
@github 에서 확인하기
/*** @site: https://www.acmicpc.net/problem/10844* @github: https://github.com/7772* @auth: Landon Park* @date: 2018. 07. 22*/#include <iostream>using namespace std;int main() {int DP[101][10] = {{0, 0},};int i, j, n, sum = 0;cin >> n;for( i = 1; i <= 9; i++) DP[1][i] = 1;for (i = 2; i <= n; i++) {for (j = 0; j <= 9; j++) {if (j == 0) DP[i][j] = DP[i - 1][j + 1] % 1000000000;else if (j == 9) DP[i][j] = DP[i - 1][j - 1] % 1000000000;else DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % 1000000000;}}for (i = 0; i <= 9; i++) sum = (sum + DP[n][i]) % 1000000000;cout << sum % 1000000000 << endl;return 0;}반응형'Algorithms > ACM_ICPC' 카테고리의 다른 글
백준 알고리즘, 2193 문제 (0) 2018.07.23 백준 알고리즘, 11057 문제 (0) 2018.07.23 백준 알고리즘, 9095 문제 (0) 2018.07.19 백준 알고리즘, 11727 문제 (1) 2018.07.19 백준 알고리즘, 11726 문제 (0) 2018.07.18