[BOJ_Python] 17626_Four Squares

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

17626번: Four Squares

 이 문제는 내가 아예 이해를 잘못해서 접근을 아예 잘못해서 틀렸다.

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의 값을 구할 때, dp리스트를 i의 제곱근까지 탐색해서 그중 최소값에 +1을 해 dp[i]에 넣는다.

 

DP알고리즘을 이용한 문제를 많이 안풀어봐서 해설을 보고 다시 풀어도 원할하지 못했던 것 같다.