[BOJ] 10844 / 쉬운 단계 수 / Python

[BOJ] 10844 / 쉬운 단계 수 / Python

[BOJ] 10844 / 쉬운 단계 수 / Python

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

풀이

처음 시도는 경우의 수가 정해져 있다고 생각하여, N 으로 구하는 점화식을 세우려고 하였다.

하지만 매우 복잡한 점화식이 세워졌고, 그 답은 보기 좋게 오답이 나왔다.

 

문제를 풀기 위한 생각의 방향은,

숫자의 자리수가 늘어날때 조건이 있고, 그 조건으로 인해 경우가 좁혀져 패턴이 발생한다는 것이다.

N = 1 -> 1 2 3 4 5 6 7 8 9

N = 2 -> 10 12
         21 23
         32 34
         43 45
         54 56
         65 67
         76 78
         87 89
         98
         
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

 

위에서 나열한 N=3 까지의 모든 경우를 패턴이 보이도록 정리해 보았다.

N = 1 ->		1	2	3	4	5	6	7	8	9
		0	1	1	1	1	1	1	1	1	1

N = 2 ->	10	21	12	23	34	45	56	67	78	89
            			32	43	54	65	76	87	98
		1	1	2	2	2	2	2	2	2	1
          
N = 3 ->	210	101	212	123	234	345	456	567	678	789
			121	232	323	434	545	656	767	878	989
			321	432	343	454	565	676	787	898
            			543	654	765	876	987
		1	3	3	4	4	4	4	4	3	2

 

끝자리 수를 기준으로 정리를 하였더니, 만들수 있는 경우의 수의 규칙이 눈이 보였다.

끝자리 수	 0 1 2 3 4 5 6 7 8 9
-----------------------------------
N = 1 -> 0 1 1 1 1 1 1 1 1 1
N = 2 -> 1 1 2 2 2 2 2 2 2 1  
N = 3 -> 1 3 3 4 4 4 4 4 3 2

어떤 숫자를 1의 자리로 만들수 있는 '계단수' 의 개수는, 그 어떤 수의 + 1 과 -1 한 숫자로 만들수 있는 이전 자리수 개수의 합.

dp 를 이차 배열로 만들었을 경우, 대각선 위의 수들의 합 : dp[N][i] = dp[N][i-1] + dp[N][i+1]

 

위의 이차원 배열과 dp 를 이용한 풀이는 다음과 같다.

N = int(input())

dp = [[0 for _ in range(10)] for _ in range(N)]

dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(1, N):
    dp[i][0] = dp[i-1][1]
    dp[i][9] = dp[i-1][8]
    for j in range(1,9):
        dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
        
print(sum(dp[N-1]) % 1000000000)

 

※ 문제를 해결하기 위한 자료구조의 다양한 형태에 대해 열린생각이 필요하다는 것을 느꼇다. 매몰되지 말자!

---

참고 블로그

https://pacific-ocean.tistory.com/151

[백준] 10844번(python 파이썬)