[BOJ][Python]17626번 풀이

https://www.acmicpc.net/problem/17626

17626번: Four Squares

import math

t = [0 for _ in range(50001)]
t[0],t[1],t[2],t[3]=0,1,2,3
for i in range(4,50001):
    minv=5
    a = math.floor(math.sqrt(i))
    for j in range(1,a+1):
        minv = min(minv, t[i-j**2]+1)
    t[i] = minv
print(t[int(input())])

아마 이게 최적화된 코드가 아닐겁니다. 막 이것저것 해보다가 성공하고 이해를 한 다음에 코드에 손을 안댔거든요. 기본 개념은 일단 dp와 브루트 포스의 융합입니다. 처음에는 그리디처럼 주어진 n에 가장 근접한 제곱을 찾고 빼는 방법을 반복하는 수식을 세우고 풀었는데 제대로 안되더라구요. 그래서 하나 하나 손으로 적으면서 해보니까 그게 통하지 않는 경우가 몇가지 있다는 걸 깨달았습니다. 가장 근접한 제곱보다 1 작은 제곱이 더 바람직한 결과를 내는 경우가 있더라구요. 사실 거기서 브루트 포스로 풀어야 한다는 걸 빨리 눈치챘어야 했는데 정말 단순하게 그럼 n-a^2이랑 n-(a-1)^2이랑만 비교하면 되겠다! 하고 헛짓거리를 계속 하고 있었습니다. 거기다 dp 특성상 초반에는 점화식이 안맞는 경우도 있다보니 예외가 좀 많네~ 하면서 하나씩 적고 있었던 것도 한 몫 했습니다. 공개된 테스트 케이스도 다 통과했다보니 맞왜틀을 반복하면서 시간을 낭비했네요.

 

위에서 적은 글들은 그냥 제가 얼마나 바보짓을 했는지에 대한 푸념입니다. 풀이가 궁금하신 분들은 위 글은 보실 필요 없어요.

 

해당 문제는 dp와 브루트 포스를 둘 다 사용하는 문제입니다. dp 문제를 몇 번 풀어보셨던 분은 이런 최적의, 가장 작은, 가장 많은 등등 여러 가지 값이 나오는 상황에서 가장 바람직한 해를 찾는 문제를 경험해보신 적이 있으실겁니다. 해당 문제도 그런 류에 속하는 문제인데요. 이 문제를 풀면서 가장 주의해야할 점은 주어진 n에 최대한 근접하는 제곱수가 항상 최적의 결과를 제공하지는 않는다는 점입니다. 해당 부분을 가장 먼저 눈치챌 수 있는 숫자는 12인데요. 12에 가장 근접하는 제곱수는 3^2=9입니다. 그렇다면 12 = 3^2 + 1^2 + 1^2 + 1^2의 4개의 자연수의 제곱의 합으로 이뤄지니까 답은 4라고 쉽게 구할 수 있는데요. 하지만 이것은 최적의 해가 아닙니다. 12 = 2^2 + 2^2 + 2^2의 3개의 자연수의 제곱의 합으로 구성할 수 있고 이게 최적의 해가 됩니다. 이렇게 우리는 주어진 n에 대해서 최적의 해를 가져다 줄 수 있는 제곱수를 찾는게 이번 문제의 핵심이 됩니다. 해당 파트가 브루트 포스가 되겠네요.

 

★n과 가장 가까운 제곱수는 항상 최적의 해로 이어지지는 않는다! 모든 수를 다 고려할 것!

 

이번엔 dp 파트를 해야겠죠. 사실 뭐 dp는 우리가 지금까지 해오던 바로 그겁니다. 앞에서 구해놓은 놈들이 최적의 해라고 확신한다면 앞에서 구한 놈들을 나중에도 쓰는거죠. 그렇다면 이번 문제에서는 어떻게 사용되는지 간단하게 한 번 봅시다. 위에서 사용했던 12를 한 번 볼까요?

 

12 = 3^2 + 3

12 = 2^2 + 8

 

이렇게 쓰니까 뭔가 보이시나요? 아직 잘 안느껴지신다면 이렇게 적어보면 어떨까요?

 

12 = 3^2 + dp[3]

12 = 2^2 + dp[8]

 

이젠 확실하게 보이실 겁니다. 주어진 수에 해당하는 해는 1 + dp[12 - i^2]로 식을 세울 수 있겠구나 하고 말이죠. 그렇다면 이제 다 했습니다. 우리는 1부터 50001까지 반복하면서 안에서는 반복문을 하나 더 사용해서 최솟값을 가져다 쓰면 됩니다.

 

사실 문제가 착안을 하면 아무것도 아닌 문제라서 최대한 생각을 하실 수 있도록 힌트를 제한하려고 했는데 너무 설명이 두루뭉실하게 들리진 않았을까 걱정이 됩니다. 혹시라도 이해가 잘안되는 부분이 있다면 언제든지 댓글로 남겨주세요.