[BOJ] 9095 1, 2, 3 더하기 Python

1, 2, 3 더하기 

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초 (추가 시간 없음)

512 MB

98786

64933

44347

64.096%

문제

정수 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

t = int(input())
graph = [[] for _ in range(12)]
graph[1] = 1
graph[2] = 2
graph[3] = 4
for i in range(4, 12):
    graph[i] = graph[i-1]+graph[i-2]+graph[i-3]
for _ in range(t):
    n = int(input())
    print(graph[n])

한시간을 고민하다 규칙을 못 떠올려 다른 풀이를 확인했다.

규칙의 힌트는 문제에 있었다.

'1, 2, 3'을 더한 수를 구하는 것이기 때문에 구하는 n번째의 3칸 앞에 3을 더해주면, 2칸 앞에 2를 더해주면, 1칸 앞에 1을 더해주면 n을 구할 수 있다.

즉, 표로 보면 이렇다.

1	2	3	4
1	(1) + 1 2	(1) + 2 (1 + 1) + 1 (2) + 1 3	-3 위치에서 합 (1) + 3 -2 위치에서 합 (1 + 1) + 2 (2) + 2 -1 위치에서 합 (1 + 2) + 1 (1 + 1 + 1) + 1 (2 + 1) + 1 (3) + 1

출처 : https://myjamong.tistory.com/302

백준 9095 파이썬 - 1,2,3 더하기 - 동적 계획법, DFS

이 규칙, 식을 스스로 떠올리는 부분이 너무 부족하다 ㅠㅠㅠ

DP문제 왜이렇게 어렵지

더 많이 풀어봐야겠다.

 

점화식 생각하기 !! 

힌트는 '문제'에 있다 !!!!