[백준 10844 파이썬/python] 쉬운 계단 수

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

풀이

1)

2)

쉬운 계단 수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	125199	39819	28800	30.067%

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

9

예제 입력 2

2

예제 출력 2

17

풀이

1)

d = [[0]*10 for _ in range(100+1)]
mod = 1000000000
n = int(input())
for i in range(1, 10):
    d[1][i] = 1
for i in range(2, n+1):
    for j in range(10):
        d[i][j] = 0
        if j-1 >= 0:
            d[i][j] += d[i-1][j-1]
        if j+1 <= 9:
            d[i][j] += d[i-1][j+1]
        d[i][j] %= mod
ans = sum(d[n]) % mod
print(ans)

1. d = [[0]*10 for _ in range(100+1)]: 2차원 리스트 d를 초기화합니다. d[i][j]는 길이가 i이고, j로 끝나는 계단 수의 개수를 저장합니다.

2. mod = 1000000000: 결과를 출력할 때 사용할 나머지 연산 상수입니다.

3. n = int(input()): 사용자로부터 입력받은 자릿수를 정수로 변환하여 n에 저장합니다.

4. 두 개의 for 반복문이 있습니다.
   • 첫 번째 for 반복문 (for i in range(1, 10))은 길이가 1인 계단 수를 초기화합니다. 길이가 1인 경우, 1부터 9까지의 숫자가 계단 수가 됩니다.
   • 두 번째 for 반복문은 다음과 같은 순서로 진행됩니다.
     1. for i in range(2, n+1): 2부터 입력받은 자릿수(n)까지 반복합니다.
     2. for j in range(10): 0부터 9까지 반복하면서 j로 끝나는 계단 수를 구합니다.
     3. d[i][j]를 0으로 초기화합니다.
     4. if j-1 >= 0: j-1이 0보다 크거나 같을 경우, 현재 길이에서 이전 길이의 j-1로 끝나는 계단 수를 더합니다.
     5. if j+1 <= 9: j+1이 9보다 작거나 같을 경우, 현재 길이에서 이전 길이의 j+1로 끝나는 계단 수를 더합니다.
     6. d[i][j] %= mod: d[i][j] 값을 mod로 나눈 나머지로 업데이트합니다.

5. ans = sum(d[n]) % mod: n자릿수에 해당하는 계단 수를 모두 합한 후, mod로 나눈 나머지를 계산하여 ans에 저장합니다.

6. print(ans): 계산된 결과를 출력합니다.

2)

n = int(input())
mod = 1000000000
d = [[0 for i in range(10)] for j in range(101)]
for i in range(1, 10):
    d[1][i] = 1
for i in range(2, n + 1):
    for j in range(10):
        if j == 0:
            d[i][j] = d[i - 1][1]
        elif j == 9:
            d[i][j] = d[i - 1][8]
        else:
            d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1]
print(sum(d[n]) % mod)

Uploaded by N2T