10844

날짜 : 2022. 11. 22

사용 언어 : python

 

문제

 

 

코드

import sys
n = int(sys.stdin.readline())
a = [[0] * 10 for i in range(n+1)]

for i in range(1, 10):
    a[1][i] = 1

for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            a[i][j] = a[i-1][j+1]
        elif j == 9:
            a[i][j] = a[i-1][j-1]
        else:
            a[i][j] = a[i-1][j-1] + a[i-1][j+1]
s = 0
for i in range(10):
    s += a[n][i]
print(s % 1000000000)

 

 

풀이

- i : 자릿수 / j : 맨 뒷자리에 오는 수로 정의했을 때 경우의 수에 대해 표를 작성하면 다음과 같이 나타난다.

	0	1	2	3	4	5	6	7	8	9	-
1	0	1	1	1	1	1	1	1	1	1	-
2	1	1	2	2	2	2	2	2	2	1	-
3	1	3	3	4	4	4	4	4	3	2	-

- 이렇게 뒷자리가 0인 경우와 0인 경우를 제외하면 이전 행의 해당숫자의 + - 1을 연산한 숫자를 더함으로써 점화식이 도출된다.

- 즉, a[i][j] = a[i-1][j-1] + a[i-1][j+1] (2 <= j < 9) 이다.

- 또한 0, 9인 경우는 각각 1과 8인 경우의 이전 행에서의 값을 더해주면 된다는 규칙성이 나타났기 때문에 분기문을 통해서 구현할 수 있다.

 

알게된 점

- 문제를 풀면서 규칙을 찾으려했지만 뒤에 붙이기보다는 앞쪽에 붙이거나 뒤에 붙이는 등 양쪽의 경우의 수를 구하려는 바람에 중복을 어찌할지 고민에 빠지게 됐고 결국 많은 시간을 허비하게 됐다.

- 해당 문제 풀이에서의 관건은 맨 마지막 수가 주어졌을 때 앞에 올 수 있는 경우를 점화식을 통해 도출해 나가는 것이었다.

- 예를들어 4자리 수 중 맨 뒷자리가 4인 경우 3번째 자리의 수는 3 또는 5가 와야 한다.

- 이 아이디어가 바로 떠오르지 못했고 결국 많은 시간을 할애하고 다른 사람의 풀이를 참고할 수 밖에 없었다ㅠㅠ

 

 

참고 사이트

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

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