-
[백준 10844번] 쉬운 계단 수백준 알고리즘 2019. 2. 28. 02:08
BOJ 10844번 쉬운 계단 수
https://www.acmicpc.net/problem/10844
백준 10844번 C++ 소스
DP배열 index를 0부터 시작해도 되지만 편의상 1자리수 일 때 1로 index를 시작하였기에
DP배열의 범위가 벗어나지 않게 여유롭게 DP[103][13]을 선언했다.
변수 i는 현재 자리수를 나타내는 변수이고,
변수 j는 0~9까지 루프를 돌게 되는데 첫자리가 아닌 끝자리가 0~9로 적용한 것이다.
끝자리가 0일때는 바로 앞자리에 1만 올 수 있고, 끝자리가 1일땐 바로 앞자리에 0또는 2가 올 수 있다.
끝자리가 9일때는 바로 앞자리에 8만 가능할 것이다.
또한, 실질적 연산은 N이 2이상 입력되었을 때 진행되며, N이 1일때는 solve함수가 실행되지 않는다.
N이 2이상 입력되었을 때 N이 1일때에 관한 DP배열 정보가 필요하므로 1자리수 일때 일일이
직접 값을 넣어주었다.
이 원리로 점화식을 세워보면 다음과 같이 3가지 경우로 나뉜다.
끝자리가 0 일 때
DP[i][j] = DP[i - 1][j + 1]
끝자리가 9 일 때
DP[i][j] = DP[i - 1][j - 1]
끝자리가 1~8 일 때
DP[i][j] = (DP[i - 1][j + 1] + DP[i - 1][j - 1])
점화식 설명 및 예시
DP[2][0]은 2자리수중 0으로 끝난다.
바로 앞자리에 숫자 1이 가능할 것이며, 이 값을 DP[1][1]에서 가져오는 방식이다.
DP[2][1]은 2자리수중 1로 끝난다.
바로 앞자리에 0 and 2가 가능할 것이며, 이 값을 DP[1][0]이랑 DP[1][2] 에서 가져오는 방식이다.
DP[1][0]은 1자리수중 0으로 끝나고, 이 값은 0이기 때문에 0으로 초기화 하고 시작했다.
ex) 3자리수 중 1로 끝나는 수는 몇 개인지 구해보기.
DP[3][1]을 구하면된다. 끝자리가 1로 끝나니깐 바로 앞 전 숫자가 0또는 2가 나와야한다.
DP[2][0] = 2자리수중 0으로 끝나는 숫자는 1개 있었음.
DP[2][2] = 2자리수중 2로 끝나는 숫자는 2개 있었음.
따라서 DP[3][1] = DP[2][0] + DP[2][2] 은
101
121
321
총 3개가 되는 것이다.
나머지연산에 관한 설명
연산과정에서 오버플로우가 발생할 수 있기 때문에 DP배열에 저장하면서 수시로 나머지연산을 하며,
DP배열을 다 채우고 마지막에 res를 더해나갈때도 오버플로우 예방을 위해 나머지연산을 해준다.
입출력 예시
45
516874370
97
549712215
13
21053
#include "pch.h" #include <iostream> #include <cmath> #include <string> #include <algorithm> using namespace std; long long solve(int N) { long long DP[103][13], res = 0; int i, j; DP[1][0] = 0; for (i = 1; i < 10; i++) { DP[1][i] = 1; } for (i = 2; i <= N; i++) { for (j = 0; j < 10; j++) { // 끝자리가 0 일 때 if (!j) { DP[i][j] = DP[i - 1][j + 1] % 1000000000; } // 끝자리가 9 일 때 else if (j == 9) { DP[i][j] = DP[i - 1][j - 1] % 1000000000; } // 끝자리가 1~8 일 때 else { DP[i][j] = (DP[i - 1][j + 1] + DP[i - 1][j - 1]) % 1000000000; } } } for (i = 0; i < 10; i++) { res += DP[N][i] % 1000000000; } return res % 1000000000; } int main(void) { int N; cin >> N; if (N == 1) { cout << 9 << endl; } else { cout << solve(N) << endl; } return 0; }
비쥬얼 스튜디오 2017.
'백준 알고리즘' 카테고리의 다른 글
[백준 1010번] 다리 놓기 (2) 2019.03.03 [백준 1018번] 체스판 다시 칠하기 (0) 2019.02.25 [백준 1912번] 연속합 (0) 2019.02.25 [백준 2473번] 세 용액 (0) 2019.02.23 댓글