[C++] 백준 10844번 쉬운 계단 수

다이나믹 프로그래밍 문제.

생각보다 너무 어려워서 이틀동안 계속 머리에 담아두다가 구글링의 도움을 받고 풀었다.

 

접근 방법

먼저, N자리 수는 

N이 1일때는 1~9

2일때는 다음과 같다.

• 맨 앞자리가 1일때 : 10, 12
• 맨 앞자리가 2일때 : 21, 23
• ...
• 맨 앞자리가 9일때 : 98

3일때는 다음과 같다.

• 맨 앞자리가 1일때 : 101, 121, 123
• 맨 앞자리가 2일때 : 210, 212, 232, 234
• ...
• 맨 앞자리가 9일때 : 987, 989

따라서 다음과 같은 정리가 가능하다.

1. 마지막 숫자가 0이라면 다음으로 갈 수 있는 수는 1 뿐이다. -> 마지막 숫자 앞의 수가 1인 경우만 마지막 숫자가 0이 가능하다.
2. 마지막 숫자가 9라면 다음으로 갈 수 있는 수는 8 뿐이다. -> 마지막 숫자 앞의 수가 8인 경우만 마지막 숫자가 9가 가능하다.
3. 마지막 숫자가 1 ~ 8이라면 다음으로 갈 수 있는 숫자는 -1, +1을 한 수이다. -> 마지막 앞의 수에 상관없이 마지막 숫자가 1 ~ 8은 두 가지 경우가 나온다.

 

즉, N개 자리수가 있을 때 각 숫자가 마지막인 경우의 개수는 다음과 같이 정리할 수 있다.

• 마지막 숫자가 0인 경우 : An = A(n-1)(1) // 마지막 숫자가 1이었던 전 자리수의 개수와 같다.
• 마지막 숫자가 9인 경우 : An = A(n-1)(8) // 마지막 숫자가 8이었던 전 자리수의 개수와 같다.
• 마지막 숫자가 1~8인 경우 : An = A(n-1)(i-1) + A(n-1)(i+1) // 마지막 숫자가 i - 1과 i + 1이었던 전 자리수의 개수들의 합과 같다.

 

문제 풀이

사용한 STL과 변수

자리수를 입력받을 n과

각 자리수마다 0~9가 얼마나 저장되어 있는지를 저장할 dp배열,

그리고 결과값을 출력할 result 변수가 있다.

 

꼭 long long 형태로 저장해주어야 Overflow 현상이 발생하지 않는다.

메인함수 - 1

우선 n을 입력받고

자리수가 1일땐 0을 제외한 모든 수의 개수가 1이므로 1로 초기화 해준다.

그리고 자리수가 2일 때부터 Bottom Up 방식으로 반복문을 돌려준다.

위에서 구한 방식으로 이중포문을 돌리면 된다.

• 마지막 숫자가 0인 경우 : An = A(n-1)(1) // 마지막 숫자가 1이었던 전 자리수의 개수와 같다.
• 마지막 숫자가 9인 경우 : An = A(n-1)(8) // 마지막 숫자가 8이었던 전 자리수의 개수와 같다.
• 마지막 숫자가 1~8인 경우 : An = A(n-1)(i-1) + A(n-1)(i+1) // 마지막 숫자가 i - 1과 i + 1이었던 전 자리수의 개수들의 합과 같다.

메인함수 - 2

그리고 결과값에 N개 자리수를 나타낼때 각 숫자가 마지막으로 얼마나 나타나는지를 저장한 배열 dp배열의 모든 수의 개수를 다 더한다.

이 때 더할때마다 모듈로 연산을 해줌으로써 오버플로우를 방지한다.

 

처음에 점화식을 엉터리로 짜고 두번째도 계속 시도했는데 쉽게 떠오르지 않았다.

그래서 구글링을 해서 어떻게 접근해야 하는지 알아본 후 풀었다.

요 근래 풀어본 실버 문제들 중 제일 생각하기 힘들었던 것 같다.

 

사실 요즘 DP문제를 많이풀어서 자신감이 붙어있던 상태였는데,

갈길이 먼 것 같다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.