다이나믹 프로그래밍(dp)
정수 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의 합으로 나타내는 방법의 수를 출력한다.
3
4
7
10
7
44
274
편의상 4, 3, 2가 써진 원을 각각 원4, 원3, 원2라고 지칭
각 원은 덧셈 식의 마지막 항이 무조건 각각 1, 2, 3인 경우를 의미함
원2에서, 2 + 3 일 때 3
을 다시 1 + 2
나 1 + 1 + 1
로도 나눠지고 그럼 다 중복되는 게 아니냐 싶었지만
두 경우는 애초에 각각 원3, 원4에 고려가 되어 있는 거라, 원2에서는 무조건 마지막에 3을 더하는 경우만 고려해서 d[2]
와 같아지는 것
같은 이유로 원4는 d[4]
, 원3은 d[3]
과 같아짐
점화식
T = int(input())
for tc in range(T):
d = [0] * 11
n = int(input())
d[1], d[2], d[3] = 1, 2, 4
for i in range(4, n+1):
d[i] = d[i-1] + d[i-2] +d[i-3]
print(d[n])
아직 대부분의 문제에서 부분 문제로 한 번 잘 나눠놓고, 그 부분 문제를 또다시 나누면서 시간을 허비하고 있음 ㅜㅅㅜ
내가 나눈 부분 문제가 무엇을 의미하는 건지 명확하게 알아야 함!