💡문제
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.
출력
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.
예제입력
2예제출력
17📖내가 작성한 Code
import sys
'''
인접한 모든 자리의 차이가 1인 수 == 계단 수
길이가 N인 계단은 총 몇개?
1,000,000,000으로 나눈 나머지를 출력
'''
MOD = 1000000000
def count_stair_number(number):
stair_number = [[0] * 10 for _ in range(number + 1)]
stair_number[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
if number == 1:
return sum(stair_number[1])
for num in range(2, number + 1):
stair_number[num][0] = stair_number[num - 1][1]
stair_number[num][9] = stair_number[num - 1][8]
for i in range(1, 9):
stair_number[num][i] = stair_number[num - 1][i - 1] + stair_number[num - 1][i + 1]
return sum(stair_number[number])
def main():
print(count_stair_number(int(sys.stdin.readline())) % MOD)
if __name__ == '__main__':
main()
✍️풀이과정
DP문제라서 뒷자리가 0,1,...,9까지인 경우로 나눈 다음 2자리까지만 해봐도 패턴을 알 수 있는 아주 쉬운 문제. 마지막 나눈 나머지를 출력하는 부분만 조심하면 된다.
주의 사항으로는 모듈러 연산을 다루는 문제에서는 항상 중간 계산에서도 모듈러를 적용해야 하는지를 문제 조건과 언어별 특성을 고려해 결정해야한다고 한다.
🧠 코드 리뷰
-
중간 계산에서 모듈러 적용 : 파이썬은 큰 정수를 자동으로 처리하지만, 정말 N이 매우 큰(수천~수만) 경우에는 중간 계산 시에도 % MOD를 취해주는 것이 안전
-
초기 조건의 별도 처리 : 이 부분을 생략하고, for문에서 range(2, number+1) 대신 range(1, number+1)와 같은 식으로 조건을 조금 다르게 잡아도 결과는 동일
-
메모리 최적화 : 만약 N이 매우 클 경우, 불필요하게 N+1 길이의 2차원 리스트를 만드는 대신, 2개의 1차원 리스트만 번갈아 가며 재사용
🛠️AI 개선 코드
import sys
MOD = 1000000000
def count_stair_number(n):
# prev[d] = "길이가 (l-1)이고, 마지막 자릿수가 d인 계단 수의 개수"
# curr[d] = "길이가 l이고, 마지막 자릿수가 d인 계단 수의 개수"
prev = [0] * 10
curr = [0] * 10
# 길이 1일 때, 마지막 숫자가 1~9인 경우 각각 1개씩
for digit in range(1, 10):
prev[digit] = 1
# 길이가 2 이상일 때부터 DP 진행
for length in range(2, n + 1):
# 0으로 끝나는 계단 수는 이전에 1로 끝나는 계단 수에서만 가능
curr[0] = prev[1] % MOD
# 9로 끝나는 계단 수는 이전에 8로 끝나는 계단 수에서만 가능
curr[9] = prev[8] % MOD
# 1~8로 끝나는 계단 수는 이전 단계 (digit-1) 혹은 (digit+1)에서 오므로
for digit in range(1, 9):
curr[digit] = (prev[digit - 1] + prev[digit + 1]) % MOD
# 다음 길이를 계산하기 위해 prev와 curr를 교체
prev, curr = curr, prev
# 길이가 n일 때 모든 끝자리의 계단 수 합
return sum(prev) % MOD
def main():
n = int(sys.stdin.readline())
print(count_stair_number(n))
if __name__ == '__main__':
main()
💻결과
🖱️참고 링크
우물 안에서 무언가 만드는 사람