(BOJ_Python) 17626_네 사각형

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

이 문제는 내가 완전히 잘못 이해하고 완전히 잘못 접근했기 때문에 잘못된 것입니다.

import math
n = int(input())

cnt = ()
while True:
    # print(int(math.sqrt(n)))
    if int(math.sqrt(n)) not in cnt:
        cnt.append(int(math.sqrt(n)))
    n -= int(math.sqrt(n)) ** 2
    # print(n)
    # print('------------')
    if n == 0:
        print(len(cnt))
        break

내 코드를 보면서 n을 더할 수 있는 제곱의 수를 세었습니다. 그래서 처음에는 무엇이 잘못되었는지조차 알 수 없었습니다.

다른 사람들이 어떻게 해결했는지 살펴보니 내가 문제를 잘못 이해하고 있었다는 것을 깨달았습니다.

올바른 응답 코드

import math

n = int(input())
dp = (0, 1)

for i in range(2, n + 1):
    minValue = 1e9
    for j in range(1, int(math.sqrt(i)) + 1):
        minValue = min(minValue, dp(i - j ** 2))
    dp.append(minValue + 1)

print(dp(n))

응답 코드를 보니 dp 방식으로 해결되었습니다. dp라는 목록의 각 인덱스에 해당하는 숫자는 추가할 수 있는 사각형 수를 나타냅니다.

1. 2에서 가장 작은 수의 제곱을 찾아 목록에 추가합니다.
2. 얻은 값은 미래 값으로 사용됩니다.
3. i의 값을 찾으면 i의 제곱근까지 dp-list를 검색하고 최소값에 +1을 더한 다음 dp(i)에 연결합니다.

DP알고리즘으로 문제를 많이 풀어본적이 없어서 설명을 읽고 풀어봐도 마음이 편치 않았습니다.