[백준] 17626번 : Four Squares [C/C++]

#문제

17626번: Four Squares

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

17626번: Four Squares

 

---

#접근방법

동적계획법을 사용하여 접근하였다.

반응형

---

#풀이

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

int dp[50005];

int main(){
    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++){
        dp[i] = dp[i-1] + 1;
        for(int j=1;j*j<=i;j++){
            dp[i] = min(dp[i],dp[i-j*j]+1);
        }
    }

    printf("%d",dp[n]);

    return 0;
}

 

동적계획법이란 특정 값을 구하기 위해 이전에 구했던 값을 재사용하는 알고리즘 설계 기법이다.

 

언듯 봤을 때는 입력한 수보다 작은 제곱수 중에서 가장 큰 값부터 구하면 제곱수들의 최소 개수가 될 것 같다고 생각을 했다.

 

하지만 예를 들어 18을 입력했을 때 18보다 작은 제곱수는 1, 4, 9, 16이다. 이 중에서 16 + 1 + 1로 구성할 수도 있지만, 9 + 9로 더 작게 구성할 수도 있어서 모든 경우의 수를 탐색해야 했다.

 

1부터 n까지 반복문을 돌면서 dp[i]에 dp[i-1] + 1을 먼저 넣어주었다. 그리고 이중 반복문으로 j변수가 i변수보다 작은 제곱수까지 반복하도록 하였다.  dp[i] = min(dp[i], dp[i-j*j]+1)로 자기보다 작은 모든 제곱수들을 탐색하면서 min함수로 최소 개수를 구해주었다.

 

그리고 dp[n]을 출력하면 제곱수들의 최소 개수가 나오게 된다.

---

#성능

---

#정리

동적계획법을 사용해야 한다는 사실,

 

이를 구현할 수 있는 구현력이 있으면 풀 수 있는 문제였다.