https://www.acmicpc.net/problem/10844
Dynamic Programming
⏰ 29분 ⏰
규칙을 찾아 점화식을 구하면 Bottom-up 방식으로 쉽게 풀 수 있는 문제입니다.
다만 저같은 경우 점화식을 구하는 데 상당한 애를 먹었습니다..
끝자리가 3인 수를 만든다고 할 때, 전단계의 끝자리 숫자는 2여나 4여야 합니다. 따라서 전단계에서 끝자리가 2였던 수의 갯수와 끝자리가 4였던 수의 갯수를 더하면 끝자리가 3인 수를 만들 수 있는 것이죠.
이를 일반화시키면
고 할 수 있습니다. 이 로직을
이차원 dp
배열을 만들어 행에는 n
(입력받은 자릿수), 열에는 0~9까지 숫자 중 각 끝자리가 몇 개씩 들어가있는지를 입력하는 방법을 통해 구현했습니다.
if __name__ == "__main__":
n = int(input())
dp = [[0]*10 for _ in range(n)]
# 첫 번째 단계 초기화
dp[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# 끝자리 수 갯수 구하기
for i in range(1, n):
# 0 은 전단계 1에서만 생성되므로
dp[i][0] = dp[i-1][1]
for j in range(1, 9):
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
# 9는 전단계 8에서만 생성되므로
dp[i][9] = dp[i-1][8]
print(sum(dp[n-1])%1000000000)
Dynamic Programming를 써서 풀어야 한다는 것은 문제를 보자 마자 알았지만, 점화식을 제대로 만드는 데 엄청난 시행착오를 겪었습니다.
애초에 원리를 생각해 보았으면 바로 점화식을 구할 수 있었을 텐데.. 그래도 이렇게 머리 박으면서 하는 과정이 실력 향상에 도움이 될 꺼라 믿습니다! (제발!)