[BEAKJOON] 백준 15990번 : 1, 2, 3 더하기 5

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

15990번: 1, 2, 3 더하기 5

문제

 

 

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

아래와 같이 몇개일지 확인을 해주었다.

# 1 - 1
# 2 - 2 : 2
# 3 - 3 : 1+2, 2+1, 3
# 4 - 3 : 1+3, 3+1, 1+2+1
# 5 - 4 : 2+3, 3+2, 2+1+2, 1+3+1
# 6 - 8 : 1+2+3, 3+2+1, 1+3+2, 2+3+1, 2+1+3, 3+1+2, 2+1+2+1, 1+2+1+2
# 7 - 9: 2+3+2, 1+2+3+1, 1+3+2+1, 2+1+3+1, 3+1+2+1, 1+3+1+2, 3+1+3, 1+2+1+3, 1+2+1+2+1

 

여기서 우리가 알아야 하는 것은, 같은 수를 두 번 이상 사용하면 안되기 때문에,

뒤에 숫자가 무엇인지를 확인해보는 과정이 필요한 것이다.

 

그러면 뒤에 숫자에 대한 확인을 어떻게 할까?

어떠한 규칙이 있어보이지는 않는다.

그러면 함수로 뒤의 숫자에 대해서 확인해주면 될 것 같다.

 

그래서 3의 크기를 가진 list로, 값을 넣어주었다.

[값 초기화]

result.append([1, 0, 0])
result.append([0, 1, 0])
result.append([1, 1, 1])

하나 이전의 값의 끝자리가 2, 3인 경우에 +1을 해주면 값이 성립한다는 뜻이다.

result[i-1][1]+result[i-1][2]

 

 

문제해결1

처음에는 "출력 초과"가 떴는데, 이는 출력 값이 너무 커졌었고,

num = int(input())
input_list = list()

for i in range(num):
    input_list.append(int(input()))

max_num = max(input_list)

result = list()
result.append([1, 0, 0])
result.append([0, 1, 0])
result.append([1, 1, 1])
result.append([2, 0, 1])
result.append([1, 2, 1])
result.append([3, 3, 2])

for i in range(6, max_num):
    result.append([result[i-1][1]+result[i-1][2],
                   result[i-2][0]+result[i-2][2],
                   result[i-3][0]+result[i-3][1]])

for i in range(num):
    print(sum(result[input_list[i]-1]))

문제의 요구사항인 "합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다."를 해주니 해결되었다.

 

문제해결2

두번째는 "시간 초과"였는데,

num = int(input())
input_list = list()

for i in range(num):
    input_list.append(int(input()))

max_num = max(input_list)

result = list()
result.append([1, 0, 0])
result.append([0, 1, 0])
result.append([1, 1, 1])
result.append([2, 0, 1])
result.append([1, 2, 1])
result.append([3, 3, 2])

for i in range(6, max_num):
    result.append([result[i-1][1]+result[i-1][2],
                   result[i-2][0]+result[i-2][2],
                   result[i-3][0]+result[i-3][1]])

for i in range(num):
    print(sum(result[input_list[i]-1])%1000000009)

이는 값들을 더할 때마다 "% 1000000009"를 해주니 해결되었다.

 

 

 

정답 코드

num = int(input())
input_list = list()

for i in range(num):
    input_list.append(int(input()))

max_num = max(input_list)

result = list()
result.append([1, 0, 0])
result.append([0, 1, 0])
result.append([1, 1, 1])
result.append([2, 0, 1])
result.append([1, 2, 1])
result.append([3, 3, 2])

for i in range(6, max_num):
    result.append([(result[i-1][1]+result[i-1][2])%1000000009,
                   (result[i-2][0]+result[i-2][2])%1000000009,
                    (result[i-3][0]+result[i-3][1])%1000000009])

for i in range(num):
    print(sum(result[input_list[i]-1])%1000000009)

 

값이 너무 커진다면, 더하는 것에도 시간의 복잡성이 커지는 것인가, 

찾아보고 추가하겠다.