BOJ #1699 제곱수의 합

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 1699. 제곱수의 합

문제 풀이

처음엔 n에서 가장 가까운 제곱수를 점차 빼나가면 해결될 수 있을 줄 알았는데 32의 경우 25 + 4 + 1 + 1+ 1의 5개항이지만 16 + 16의 2개항으로도 나타낼 수 있기 때문에 무작정 큰 제곱수를 빼나가면 오답을 출력한다. 그렇기 때문에 각 제곱수에 대해 모두 체크한 뒤 그 가운데 최소값을 구해야 했다. 난이도가 꽤 있었던 DP 문제로 아직 미숙했던 것 같다.

python 코드

n = int(input())
dp = [i for i in range(n + 1)] # dp 맵 매핑
board = [i * i for i in range(318)] # 제곱수 기록
for i in range(1, n + 1): # dp맵 각 항에 대해
    s = [] # 버퍼 리스트
    for j in board: # 각 제곱수에 대해
        if j > i: # 제곱수가 인덱스 초과 시 skip
            break
        s.append(dp[i - j]) # i - 제곱수 좌표 더하기
    dp[i] = min(s) + 1 # 버퍼 리스트 중 최소값 + 1
    # +1은 앞의 제곱수 for문에서 뺏던 제곱수 몫이다.
print(dp[n])