BOJ 17626번: Four Squares

 

www.acmicpc.net/problem/17626

17626번: Four Squares

문제풀이:

DP를 이용해서.. 1부터 N까지 숫자의 최소 표현 개수를 모두 구한다.

구하는 방법을 생각해내는 게 어려웠는데, dp[0]=0, dp[1]=1 이라는 초기값을 넣어주고

2~N까지 i를 돌면서 i에서 i보다 같거나 작은 제곱 수를 하나씩 빼면서 최솟값을 갱신하는 방식으로 풀었다.

그래서 제곱 수의 배열인 arr도 따로 만들었고, 제곱한 값이 N보다 같거나 작은 경우만 넣었다.

그리고 마지막에 DP에 저장할 때는 최솟값 + 1을 저장한다. arr[j]를 더한 것을 카운트 해야 하기 떄문..?!

dp[N]를 최종 출력하면 된다.

 

import sys
import math
input = sys.stdin.readline

N = int(input())


n = math.floor(N**0.5)

arr = []
for i in range(n+1):
    arr.append(i*i)

dp = [5]*50001
dp[0] = 0
dp[1] = 1
for i in range(2, N+1):
    minNum = 5;

    for j in range(math.floor(i**0.5)+1):
        tmp = i - arr[j]
        minNum = min(minNum, dp[tmp])
    dp[i] = minNum + 1

print(dp[N])

        

 

막혔던 부분? dp 초기화를 0으로 했더니 모든 값이 1로 나오는 기적.. 그리고 dp 크기를 arr 크기랑 똑같이 했더니 인덱스  오류...