백준: 10844 쉬운 계단 수

문제

10844번: 쉬운 계단 수

 

문제 풀이

 수의 길이가 1인 경우에는 1 - 9 까지의 계단수가 있으므로 경우의 수는 9개이다. 수의 길이가 2인 경우에는 다음과 같은 경우의 수들이 있다.

시작 수	1	2	3	4	5	6	7	8	9
	10	21	32	43	54	65	76	87	98
		23	34	45	56	67	78	89

 표를 보면 시작하는 수가 1과 9를 제외하고는 시작 수가 가질 수는 경우의 수는 다음과 같이 코드로 나타낼 수 있다.

cur = [
  cur[1],
  cur[0] + cur[2],
  cur[1] + cur[3],
  cur[2] + cur[4],
  cur[3] + cur[5],
  cur[4] + cur[6],
  cur[5] + cur[7],
  cur[6] + cur[8],
  cur[7] + cur[9],
  cur[8]
]

 즉 시작 수(인덱스) 처음과 끝을 제외하고는 이전의 수와 다음의 수에 영향을 받는 것을 알 수 있다. 따라서 이전의 값을 기준으로 다음값을 계산하기 위한 과정을 위의 리스트와 같이 처리하면 정답을 도출할 수 있다.

 

코드

from sys import stdin

if __name__ == '__main__':
    n = int(stdin.readline())
    cur = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

    for _ in range(n - 1):
        tmp = cur.copy()
        cur[0] = tmp[1]
        for i in range(1, 9):
            cur[i] = tmp[i - 1] + tmp[i + 1]
        cur[9] = tmp[8]
    print(sum(cur))