[백준] 10844번 : 쉬운 계단 수

 

 

 

 

 

접근법

- 배열의 사이즈를 10 X 101(i = 0인 배열은 편의 상 안 쓰기 위해 101로 만듦)로 만들었다.

 

- 예제 입력 1번을 위해 l[1][0]을 제외한 l의 1행에 1 값을 넣어주었다.(l[1][0]은 0으로 시작하는 수는 없기 때문에 0으로 설정)

 

- l[2]부터는 이전 배열의 값들을 참고하여 넣는다.

 

- l[i][0]의 경우 l[i][1]의 경우 밖에 생길 수 없으므로 l[i][j] = l[i - 1][j + 1]을 적용한다.

 

- l[i][9]의 경우 l[i][8]의 경우 밖에 생길 수 없으므로 l[i][j] = l[i - 1][j - 1]을 적용한다.

 

- 그 외의 경우에는 자신보다 작은 값에서 1개, 큰 값에서 1개기 때문에 l[i][j] = l[i - 1][j - 1] + l[i - 1][j + 1]을 적용한다.

 

ex) l[7][7]은 l[6]에서 끝자리가 6이나 8이었던 l[6][8]과 l[6][6]을 더한 값이 된다.

 

- N행의 모든 값을 sum을 이용하여 합계를 계산하고 1,000,000,000으로 나눈 나머지를 출력한다.

 

 

 

 

 

 

풀이

# 백준 10844번, 쉬운 계단 수

N = int(input())
l = [[0 for _ in range(10)] for _ in range(101)]

for i in range(len(l[1])) :
    if i == 0 :
        l[1][i] = 0
    else :
        l[1][i] = 1

for i in range(2, N + 1) :
    for j in range(10) :
        if j == 0 :
            l[i][j] = (l[i - 1][j + 1])
        elif j == 9 :
            l[i][j] = (l[i - 1][j - 1])
        else :
            l[i][j] = (l[i - 1][j + 1] + l[i - 1][j - 1])

print(sum(l[N]) % 1000000000)

 

 

 

 

 

 

 

결과