[백준] 10844번 : 쉬운 계단 수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

10844번: 쉬운 계단 수

 

1. 문제 설명

2. 풀이과정

해당 문제는 원하는 자릿수의 계단 수의 개수를 구하는 문제이다.

마지막 숫자의 값에 따라 다음으로 올 수 있는 수가 결정된다.

처음에는 자릿수를 늘려가며 계단 수를 모두 구하는 방식으로 풀이하였다.

하지만 메모리 초과가 계속적으로 발생하였다.

 

하여 고정된 메모리를 사용하고 최소한의 메모리를 사용할 방법을 고안해 보았다.

0과 9는 1가지, 나머지 숫자는 2가지씩 다음 숫자가 올 수 있다.

해당 숫자가 마지막 숫자로 올 수 있는 경우의 수는 이전 결과에서 해당 숫자가 마지막으로 올 수 있는 경우의 수를 더하면 된다.

예를 들어 다음 결과에서 마지막 숫자가 1인 경우의 수는 이전 결과에서 0과 2의 경우의 수의 합이다.

이를 활용하여 계속적으로 마지막 숫자의 개수를 구할 수 있고 마지막 숫자의 총 개수가 정답이 된다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. N을 입력받는다. N = int(sys.stdin.readline())
3. 각 숫자별 다음에 올 수 있는 숫자의 개수를 저장한다. case = [1, 2, 2, 2, 2, 2, 2, 2, 2, 1]
4. N이 1일 때 각 숫자가 마지막 숫자일 경우의 수를 저장한다. count = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
5. N이 1일 때의 결과는 이미 저장했으므로 다음 차례부터 반복한다. for _ in range(N - 1)
6. 다음 결과의 마지막 숫자의 개수를 저장할 리스트를 생성한다. next = [0 for i in range(10)]
7. 마지막으로 올 수 있는 숫자는 10개이므로 10번 반복하며 for i in range(10)
8. 다음으로 0이 마지막 숫자로 올 수 있는 경우는 1에서 오는 경우뿐이다. if (i == 0): next[i] = count[i + 1]
9. 다음으로 9가 마지막 숫자로 올 수 있는 경우는 8에서 오는 경우뿐이다. elif (i == 9): next[i] = count[i - 1]
10. 그 외 나머지 1~8이 마지막 숫자로 올 수 있는 경우는 else
11. 각각 앞 뒤 숫자 2가지에서 올 수 있다. next[i] = count[i - 1] + count[i + 1]
12. 다음 경우의 각 숫자가 마지막 숫자일 경우의 수를 새로 저장한다. count = next
13. 구하려고 하는 자릿수의 값까지 구했으면 마지막 숫자의 각 개수의 합이 최종 결과가 된다. answer = sum(count)
14. 결과를 1,000,000,000으로 나눈 나머지를 출력한다. print(answer % 1000000000)

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

case = [1, 2, 2, 2, 2, 2, 2, 2, 2, 1]
count = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for _ in range(N - 1):
    next = [0 for i in range(10)]
    for i in range(10):
        if (i == 0):
            next[i] = count[i + 1]
        elif (i == 9):
            next[i] = count[i - 1]
        else:
            next[i] = count[i - 1] + count[i + 1]

    count = next

answer = sum(count)
print(answer % 1000000000)