백준 10844 파이썬

 

10844번: 쉬운 계단 수

 

 

정답 코드 

N = int(input())
array = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
board = []
if N == 1:
    print(9)
    exit()
else:
    board.append(array)
    for n in range(1, N):
        temp = []
        for j in range(10):
            if j == 0:
                temp.append((board[n - 1][1]))
            elif j == 9:
                temp.append((board[n - 1][8]))
            else:
                temp.append((board[n - 1][j - 1] + board[n - 1][j + 1]))
        board.append(temp)
print(sum(board[-1]) % 1000000000)

 

 

접근 사고

 

N 자리 수 일 때 어떤 숫자로 끝나냐에 따른 경우의 수를 정리한 테이블이다.

예를 들어 N = 2 는 두 자리수 자연수를 뜻한다. N = 2 일 때 끝자리 숫자가 3이라면, 나올 수 있는 경우의 수가 2개라는 뜻이다 ( => 23, 43) 

마찬가지로 N = 3 일 때 끝자리가 9 라면, 나올 수 있는 경우의 수는 2이다. (=> 789, 989) 

저런 테이블은 어떻게 동적으로 채워나갈 수 있을까? dp 를 계속 풀면서 느끼는 건 문제 속에 항상 모종의 규칙성이 숨어있다. 끝자리 숫자가 0 과 9 일 때를 제외하곤, n 행의 1 에서 8까지의 숫자(m)는 이전 행(n - 1)의 양 사이드 (m - 1, m + 1)  의 합이 된다. 

즉 0 과 9일 때만 따로 계산하고, 1 ~ 8 에 해당되는 경우는 이전 행의 양 사이드에서 더해오면 된다. 이것을 식으로 표현하면 된다!