[구름톤 챌린지] Day 11 - 통증2(동적 프로그래밍)

https://level.goorm.io/exam/195693/%ED%86%B5%EC%A6%9D-2/quiz/1

구름LEVEL

---

문제

---

풀이

동적프로그래밍 문제로 재귀함수를 이용해서 풀어야하는 것이 정석인데 구현으로 풀게 되었다. DP로 푸는 방법도 알아두자.

# 1. 작은수로 나누어지거나 안나누어질때는 바로 결과값 return
# 2. 큰수보다 작은 n인데 a로 나누어지면 몫, 안나누어지면 -1
# 3. n이 b보다 클때, 최대 몫 구하고 그 나머지가 a로 나누어지면 몫 더하기 안된다면 몫에서 -1하면서 a로 나누어지는지 확인
import copy

def sol():
	n = int(input())
	a,b = map(int,input().split())

	first = copy.deepcopy(n)

	res = 0
	if n < a:
		return -1
	elif n == a :
		return 1
	if n < b:
		if n%a == 0:
			return n//a
		else:
			return -1
		
	while n>=b:
		if n>=b:
			res += n//b
			n %= b
	# 여기서 a로 안나눠질때
	if n%a == 0:
		res += n//a
		n = 0
	if n > 0:
		while True:
			res -= 1
			if (first-(res*b))%a == 0:
				# print(res,(first-(res*b))//a)
				return res+(first-(res*b))//a
				break
			if res < 1:
				return -1
				break

	else:
		return res
	
ans = sol()
print(ans)

1. 작은수로 나누어지거나 안나누어질때는 바로 결과값 return
2. 큰수보다 작은 n인데 a로 나누어지면 몫, 안나누어지면 -1
3. n이 b보다 클때, 최대 몫 구하고 그 나머지가 a로 나누어지면 몫 더하기 안된다면 몫에서 -1하면서 a로 나누어지는지 확인