Baekjoon15990 - 1,2,3 더하기5(Python)

백준 사이트 15990 - 1,2,3 더하기5 문제입니다.

이 글을 보시기 전에 문제를 풀기 위해 충분한 생각을 하셨나요? 답을 안 보고 푸는게 최대한 고민하는게 가장 중요하다고 생각합니다.!!

☑️ 1. 문제

https://www.acmicpc.net/problem/15990

---

☑️ 2. Input , Output

---

☑️ 3. 분류 및 난이도

코딩테스트 준비-기초 : 브루트포스 - 다이나믹프로그래밍 문제입니다.

---

☑️ 4. 생각한 것들

• 3가지 경우의 수가 있습니다. 1의 경우 [1]

2의 경우 [2]

3의 경우 [3], [1+2], [2+1]의 경우의 수를 가지고 각 자리수가 1,2,3으로 끝납니다.

다음 4를 계산할 때 [1+2+1], [1+3],[3+1]로 되는데

이런식으로 끝이 나온 숫자를 표로 나타내면

끝이/n	1	2	3	4	5
1	1	0	1	2	1
2	0	1	1	0	2
3	0	0	1	1	1

여기서 식을 세울 수 있습니다. 5의 경우 4의 경우의 수에 1을 더하면 되는데 연속해서 1이 나올 수 없으므로 끝자리가 2이거나 3인 경우인 경우의 수에 1을 더하면 됩니다. 그래서 4의 경우의 수에서 끝자리가 2인 경우의 수 (0)과 끝자리가 3인 경우의 수 (1)을 합한 0+1의 경우의 수에 1을 더한 값이 5의 경우의 수중에 끝자리가 1인 경우에 포함됩니다.

마찬가지로 5의 경우의 수 중 끝자리가 2인 경우의 수는 3+2가 5이므로 3의 경우의 수를 살펴봐야하는데, 연속된 숫자가 나오면 안되므로 3의 경우의수 중 끝자리가 1과 3으로 끝나는 것에 2를 더하면 됩니다. 그래서 3의 경우의 수중 끝자리가 1인 경우의수 1과 3으로 끝나는 경우의 수 1을 합한 2가 5의 끝자리가 2인 경우의 수가 되는거죠.(3+2), (2+1+2)

이런식으로 접근하면 풀 수 있습니다.

• 시간 효율성을 고려하여 애초에 최대 경우의 수인 100,000크기의 메모제이션을 쓰지 않았고, 들어온 인풋값중 제일 큰것을 찾고 그 크기만큼 메모제이션을 수행하였습니다. 최악의 경우는 어차피 똑같겠지만요.

파이썬은 정수길이에 제한이 없어서 매 번 나눠줘야합니다.

---

5. code

from sys import stdin

mod = 1000000009
t = int(stdin.readline())

input_list = []
for i in range(t):
    input_list.append(int(stdin.readline()))
max_num = max(input_list) + 1

dp_one = [0] * max_num
dp_two = [0] * max_num
dp_three = [0] * max_num

dp_one[1] = 1
dp_one[3] = 1
dp_two[2] = 1
dp_two[3] = 1
dp_three[3] = 1

for i in range(4, max_num):
    dp_one[i] = (dp_two[i - 1] + dp_three[i - 1]) % mod
    dp_two[i] = (dp_one[i - 2] + dp_three[i - 2]) % mod
    dp_three[i] = (dp_one[i - 3] + dp_two[i - 3]) % mod

for result in input_list:
    print((dp_one[result] + dp_two[result] + dp_three[result]) % mod)

---

6. 후기

c++로 작성이 필요하거나 도움이 필요하시면 댓글을 작성해주세요.!! 기록용이라 설명이 자세하지 않습니다.