[백준(BOJ)] 1699번: 제곱수의 합 (Dynamic Programming, C++)

📝 문제풀이 과정

---

• DP[i] : 숫자 i에서 제곱수 항 최소 개수
• 주의할 점이, 지금까지 항상 인덱스 0부터 시작해서 0을 숫자 1로 해서 하려고 했는데, 7 이상부터는 수가 잘 안 맞았다. +1을 하면 7 이전 숫자들에서 안 맞고, 1을 더하지 않으면 7부터가 안 맞는다.
• 그래서 인덱스를 숫자 그대로 했더니, DP[i] = min(DP[i], DP[i-j*j]+1)에서 4에서는 DP[4-2*2] + 1 = 0 + 1 =1, 7도 DP[7-4] + 1 = 4로 제대로 나온다.
• j*j <= i 범위의 반복문을 통해 DP[i]를 1로만 항을 구성했을 때와 DP[i-j*j] + 1에서 최솟값을 DP[i]로 가져간다.

DP[1] = min(1, DP[0]+1) = 1
DP[2] = min(2, DP[2-1]+1) = 2
DP[3] = min(3, DP[3-1]+1) = 3
DP[4] = min(4, DP[4-2*2]+1) = 1
DP[5]: 2
DP[6]: 3
DP[7]: 4
DP[8]: 2
DP[9]: 1
DP[10]: 2
DP[11]: 3

 

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <algorithm>
#include <deque>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);

    deque<int> DP(N+1, 0);

    for(int i=1; i<=N; i++){
        DP[i] = i; // 1로만 구성했을 때 개수로 초기화
        for(int j=1; j*j <= i; j++){
            DP[i] = min(DP[i], DP[i-j*j]+1);
        }
    }
    printf("%d", DP[N]);
    
}

 

 

👏 결과

---