문제들
15989: 1, 2, 3 더하기 4
정수 4를 1, 2, 3의 합으로 나타내는 네 가지 방법이 있습니다. 합계를 표현할 때 둘 이상의 숫자를 사용해야 합니다. 합의 순서만 다른 숫자는 같은 것으로 간주됩니다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2
www.acmicpc.net
해결 방법
– DP로 해결했습니다.
– 재귀공식을 노트를 통해 발견하면 쉽게 풀 수 있는 문제
– 1, 2, 3에서 4를 만들려면 1이 될 수 있는 수에 3을 더하고, 2가 될 수 있는 수에 2를 더하고, 3이 될 수 있는 수에 1을 더하면 됩니다.
– 즉, 재귀식 dp(4) = dp(1) + dp(2) + dp(3)을 얻을 수 있다.
– 다만, 문제에서 합을 이루는 숫자의 순서만 다르다고 하므로 같은 것으로 간주하여 중복을 제거하여야 한다.
– 중복을 제거할 때 간단한 공식을 찾을 수 있습니다. dp(n)을 찾으려면 dp(n-3)에 중복이 없으므로 먼저 dp(n-2)에서 모두 더하고 중복을 제거합니다. n // 조합이 2개밖에 없음을 알 수 있습니다.
– 마지막으로 dp(n-1)의 경우 중복 제거 후 1+1+…+1 한 개만 남아 있으므로 항상 1개의 조합이 있습니다.
– 즉, 중복을 제거한 dp(n)을 계산하는 공식은 dp(n-3) + n // 2 + 1입니다.
아래는 솔루션 코드입니다.
# 1,2,3 더하기 4
# 제출시 재귀 호출 초과로 런타임에러가 발생하여 재귀 호출 제한을 10000회로 설정하였음.
import sys
sys.setrecursionlimit(10000)
def find(number):
if dp(number) != 0:
return dp(number)
dp(number) = find(number - 3) + (number // 2) + 1
return dp(number)
t = int(input())
for _ in range
n = int(input())
dp = (0, 1, 2, 3) + (0 for _ in range(n - 3))
print(find(n))