구름톤 챌린지 11번 통증(2)

https://level.goorm.io/l/challenge/goormthon-challenge

통증 1문제는 a랑 b랑 서로 배수형태엿지만 해당 문제는
2 <= a,b <= 13
인 경우라서 다른 접근이 필요하다.

dp라고 적혀있어서 단순 dp로 풀었지만 시간초과에 재귀 깊이 초과에 난리였따...

다른 방법이 있지 않을까 하다가 생각해 본 것은 순서가 상관 없다는 것이엿다 즉

a = 2
b = 5일경우
aaab 를 골른 결과랑 abaa baaa 다 같은결과이다.. 즉 냅색 문제와 관련 있을 것이라 생각햇다..

https://velog.io/@jxlhe46/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C-Knapsack-Problem
그래서 블로그를 참고해서 풀었는데 코드는 다음과 같다.

# -*- coding: utf-8 -*-
# UTF-8 encoding when using korean

n = int(input())
a,b = map(int, input().split())
dp = [[-1,-1] for i in range(10**6+1)]
dp[0] = [0,0]

for i in range(n+1):
	if a <= i:
		if dp[i-a][0] != -1 and dp[i-a][1] != -1:
			dp[i][0] = min(dp[i-a][0] + 1, dp[i-a][1] + 1)
            
		elif dp[i-a][0] != -1:
			dp[i][0] = dp[i-a][0] + 1
            
		elif dp[i-a][1] != -1:
			dp[i][1] = dp[i-a][1] + 1
            
	if b <= i:
		if dp[i-b][0] != -1 and dp[i-b][1] !=-1:
			dp[i][0] = min(dp[i-b][0] + 1, dp[i-b][1] + 1)
            
		elif dp[i-b][0] != -1:
			dp[i][0] = dp[i-b][0] + 1
            
		elif dp[i-b][1] != -1:
			dp[i][1] = dp[i-b][1] + 1
			
if dp[n] == [-1,-1]:
	print(-1)
elif dp[n][0] == -1:
	print(dp[n][1])
elif dp[n][1] == -1:
	print(dp[n][0])
else:
	print(min(dp[n]))
		

코드는 간단하다 -a 칸과 -b칸의 0과 1중에 최소값을 선택하고,
-1이면 무시하는 코드이다...
결과도 만들 수 없는 경우일 떄 -1로 처리해 주었따..