[백준] 9095 : 1, 2, 3 더하기

문제

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

9095번: 1, 2, 3 더하기

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

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

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

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

코드

import sys
input = sys.stdin.readline

n = int(input())
for _ in range(n):
    k = int(input())
    if k == 1:
        print(1)
    elif k == 2:
        print(2)
    elif k == 3:
        print(4)
    else:
        answer = [0]*(k+1)
        answer[1] = 1
        answer[2] = 2
        answer[3] = 4
        for i in range(4, k+1):
            answer[i] = answer[i-1] + answer[i-2] + answer[i-3]
        print(answer[k])

 

n이 1, 2, 3일 때는 방법의 수를 간단히 구할 수 있고 이 값을 n이 4 이상인 경우부터 사용해야 하기 때문에 미리 배열에 저장해둔다.

n이 4 이상인 경우부터

(n-1의 경우의 수에 1을 더한 경우) + (n-2의 경우의 수에 2를 더한 경우) + (n-3의 경우의 수에 3을 더한 경우)

가 답이 된다.

예를 들어, n = 4 일때

1+1+1 / 1+2 / 2+1 / 3   ->    n = 3 인 경우의 끝에 1을 더한 경우

1 + 1 / 2   ->   n = 2 인 경우의 끝에 2를 더한 경우

1   ->   n = 1 인 경우우의 끝에 3을 더한 경우

들의 합인 7이 정답이 된다.

 

 

오랜만에 !!!! 나 혼자 뚝딱 풀고 제출했더니 맞았던 문제 !!!

저번 동적 프로그래밍 문제 풀면서, 동적 프로그래밍 생각이 안 나서 결국 복잡하게 구현하다가 시간초과가 났었다.

이번에는 문제 보자마자 동적 프로그래밍 생각이 났구, 그대로 풀어보니 정답이 나왔다.

동적 프로그래밍 문제 중에서 기본 중의 기본 문제지만 그래도 뿌듯뿌..ㅎㅎ