Leetcode 279. Perfect Squares
문제 개요
0이상 정수 N이 주어진다. 제곱(square)수들의 조합을 이용하여 정수 N을 만들 수 있는 최소 방법의 수를 구해야 한다.
예시
N = 12일 경우, 만들 수 있는 가지 수는 아래와 같다.
문제 분석
위의 예시와 같이 N보다 작은 최대 제곱수부터 계산 해도 최소 값이 나오지 않는다. 따라서 Greed Search로는 풀 수 없고, 대신 Dynamic Programming을 이용하여 해결할 필요가 있다.
Cache 디자인
Dynamic Programming은 문제의 결과 값을 미리 저장한 후 현재의 문제를 작은 문제로 나뉘어 미리 저장한 값을 이용해 해결해 나가는 것이다.
N보다 작은 수들의 결과 값을 저장하여 N까지 도달하면 결과값을 얻어보자.
문제 나누기
문제는 아래와 같이 나눌 수 있다.
* cache[n] = 정수 N의 결과 값
cache[0] = 0
*N이 지수일 경우*
cache[1] = 1
cache[4] = 1
cache[9] = 1
*N이 지수가 아닐 경우*
cache[2] = cache[2 - 1] + 1
cache[3] = cache[3 - 1] + 1
cache[5] = min(cache[5 - 4] + 1, cache[5 - 1] + 1)
cache[6] = min(cache[6 - 4] + 1, cache[6 - 1] + 1)
cache[7] = min(cache[7 - 4] + 1, cache[7 - 1] + 1)
cache[8] = min(cache[8 - 4] + 1, cache[8 - 1] + 1)
cache[10] = min(cache[10 - 9] + 1, cache[10 - 4] + 1, cache[10 - 1] + 1)
...
cache[11] = min(cache[11 - 9] + 1, cache[11 - 4] + 1, cache[11 - 1] + 1)
cache[12] = min(cache[12 - 9] + 1, cache[12 - 4] + 1, cache[12 - 1] + 1)
제일 직관적으로 알 수 있는 사실은 N이 지수일 경우 최소 가지수는 1가지 이다.
그러나, N이 지수가 아닐 경우 N보다 작은 지수들을 빼면서 가지수를 1가지 늘린 후 N보다 작은 결과값을 바탕으로 최소값을 구해야 한다.
해결 전략
def perfectSquares(n: int) -> int:
def square(number: int):
return number ** 2
# cache를 최대 가지수로 설정 (전부 1을 이용하여 만들 경우)
cache = [ max_result for max_result in range(0, n + 1) ]
for current_number in range(1, n + 1):
start_square_number = 1
minimum_result = cache[current_number]
while current_number - square(start_square_number) >= 0:
# current_number가 지수일 경우
if square(start_square_number) == current_number:
minimum_result = 1
break
# current_number가 지수가 아닐 경우
miminum_result = min(
minimum_result,
cache[current_number - square(start_square_number)] + 1)
start_square_number += 1
# n보다 작은 수들의 결과 값을 반영
cache[current_number] = minimum_result
return cache[n]