boj 9095 : 1, 2, 3 더하기

문제 주소: https://www.acmicpc.net/problem/9095

난이도: silver 3

1.문제설명

• 정수 n이 주어졌을 때, n을 1,2,3 의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오
• 테스트케이스의 개수가 주어지고
• 그만큼 n이 입력된다.

2.문제해결 아이디어.

• n은 양수이며 11보다 작다고 한다.
• 또한 이는 최적화 문제가 아니다
• memoization을 활용하는 문제다.
• 따라서 하나의 cache테이블을 만들고 활용하도록 하자

3.문제접근법

• n = [1, 10] 이다 따라서 11칸을 가진 리스트를 만든다. (0번째 인덱스는 사용안함)
• 캐시테이블을 초기화하자
• cache[i] 는 i를 1,2,3의 합으로 나타내는 경우의 수이다.

cache = [1e9] * 11
cache[1] = 1
cache[2] = 2
cache[3] = 4

• 4부터 10까지 아래 점화식을 점화한다.

cache[i] = (cache[i-1]) + (cache[i-2]) + (cache[i-3])

• i를 만드는 방법은
  • i에서 1을 뺀 수를 만들고, 단순히 1만 더해주면 되기 때문에 cache[i-1]가지 경우
  • i에서 2를 뺀 수를 만들고, 단순히 2만 더해주면 되기 때문에 cache[i-2]가지 경우
  • i에서 3을 뺀 수를 만들고, 단순히 3만 더해주면 되기 때문에 cache[i-3]가지 경우

4.특별히 참고할 사항

• dp를 이용한 최적화 문제가 아니라
• memoization을 이용하는 문제였다.

5.코드구현

T = int(input())
question = []
for i in range(T):
    question.append(int(input()))
cache = [1e9] * 11
cache[1] = 1
cache[2] = 2
cache[3] = 4
for i in range(4,11):
    cache[i] = (cache[i-1]) + (cache[i-2]) + (cache[i-3])
for q in question:
    print(cache[q])