[BOJ 백준] 10844번 - 쉬운계단수 (C++ ,JAVA)

출처 : www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

45656 이라는 수가 있을때, 각 자리수와 인접한 숫자들의 차이가 모두 1인 숫자들을 계단 수 라고 한다.

자리수가 N인 숫자들중에서 계단 수가 몇개가 있는지 계산하는 문제이다.

 

정답을 10억으로 나눈 나머지를 출력해야한다.

접근

접근 요약(급하다면)

수의길이를 N이라고 하고 N>=2이며, 1의 자리수가 x,y인 수의 갯수 배열을 axy[N]이라고 한다면

아래 설명대로라면 1차원 배열을 5개 만들어야함 (혹은 2차원배열을 만들어도 상관없음)

 

a09[N] = a18[N-1] % (1000000000)

a18[N] = (a09[N-1] + a27[N-1]) % (1000000000)
a27[N] = (a18[N-1] + a36[N-1]) % (1000000000)
a36[N] = (a27[N-1] + a45[N-1]) % (1000000000)
a45[N] = (a36[N-1] + a45[N-1]) % (1000000000)

 

a09[N] + a18[N] + a27[N] + a36[N] + a45[N] 의 값이

길이가 N일때 계단수의 갯수가 된다.

 

각 axy[N]의 값을 저장할때부터 왜 10억으로 나누는가?

나누어주지 않으면 axy[N]에 저장되는 값이 엄청커지기때문에 나중에 정답을 10억으로 나눌때 전혀 다른 값이 나오게 된다.

 

N=2일때 

a09[2] = a09[1] (1) % 10억

a18[2] = a09[1] (1) + a27[1] (2) % 10억

a27[2] = a18[1] (2) + a36[1] (2) % 10억

a36[2] = a27[1] (2) + a45[1] (2) % 10억

a45[2] = a36[1] (2) + a45[1] (2) % 10억

 

이 되며, a09[N] ~ a45[N] 까지의 합이 수의 길이가 N일때 계단수의 갯수가 된다.

 

왜 이렇게 요약되었는지 궁금하면 아래 내용을 보면 된다.

 

설명

N이 1,2,3,4일때까지는 직접 써보며 규칙을 찾아봤다.

 

N이 1일때는

1 2 3 4 5 6 7 8 9

1~9까지 9개이다. (0으로 시작하는 수는 없으므로 0은 제외)

 

N이 2일때는 

10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98

총 17개이다. (마지막 9에서는 98만 가능하다. 90이 가능했다면 총 18개이어야 하지만 예제에서도 17로 나오는것을 보면 마지막 자리수가 9일때는 1개만 가능한것으로 보인다.)

 

N이 3일때는

101 121 123 210 212 232 234 321 323 343 345 432 434 454 456 543 545 565 567 654 656 676 678 765 767 787 789 876 878 898 987 989

총 32개이다.

 

N이 3일때까지 계산하고나서 이렇게 생각을 해봤다.

N자리수에서 1의자리 수가 0 또는 9일때는 N+1자리수가 되었을때 계단수가 1개만 나오고,

그 이외의 숫자일경우에는 계단수가 2개가 나온다.

 

예를들어, N이 2일때 1의자리수가 0 또는 9인 경우는 10, 89 두가지였는데

N이 3이되었을때 101, 898 이 되었다. 그 이외의 경우에는 각각 두가지의 계단수가 생성되었다.

 

N자리수 숫자의 1의 자리수가 0 또는 9인 수의 갯수 + 1 또는 8 + 2 또는 7 + 3 또는 6 + 4 또는 5 의 수의 총합이

N의 계단수가 된다.

 

N이 2일때

1의 자리수가 0또는 9인 수의 개수 : 10 89  -> 2개

1의 자리수가 1또는 8인 수의 개수 : 21 78 98   -> 3개

1의 자리수가 2또는 7인 수의 개수 : 12 32 67 87 -> 4개

1의 자리수가 3또는 6인 수의 개수 : 23 43 56 76 -> 4개

1의 자리수가 4또는 5인 수의 개수 : 34 54 45 65 -> 4개

총 17개이다.

 

그럼 N자리수의 1의 자리수가 0 또는 9인 경우는 어떻게 찾을까?

바로 N-1자리수의 1 또는 8인 경우의 갯수가 N자리수의 1의 자리수가 0 또는 9가 되는 경우이다.

N-1자리수에서의 1이 N자리에서 0이 되고, 8이 N자리에서 9가 되기 때문이다.

 

또 1의 자리수가 1 또는 8인 경우는 어떻게 찾을까?

N-1자리수의 0 또는 9인경우의 수 + 2 또는 7인 경우의 수가 되고...

 

그러다보면 앞선 요약설명과 같은 식이 완성된다.

 

이런식으로 각각의 자리수의 갯수를 총 합한것이 N자리수의 총 계단수가 된다.

 

 

코드

Java : github.com/devdinist/BOJ_Code/blob/master/Java/Sort_Algorithm/DP/BOJ10844.java

devdinist/BOJ_Code

Cpp : github.com/devdinist/BOJ_Code/blob/master/Cpp/DP/BOJ10844.cpp

devdinist/BOJ_Code