[BOJ] 백준 1699 제곱수의 합 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

1. 어떤 자연수 N 은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다.

2. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구해야 한다.

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

 

 

💭 풀이 과정

 

 

DP 방식을 활용하기로 하면서 제곱수가 1 로만 구성되어있을 때, 1, 2 로 구성되어 있을 때, 1, 2, 3 으로 구성되어 있을 때 .... 등등

 

순차적으로 하나 씩 포함하며 모든 경우를 따져보기로 했다.

 

N 이 15 인 경우를 예로 들어보자면 다음과 같다.

 

 

 

 

< 1 의 제곱수들의 합으로 만들 때 항의 수 >

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

 

각 인덱스가 입력으로 받는 자연수 N 이다.

N = 5 의 경우  1² + 1² + 1² + 1² + 1² = 5  이므로 다섯 개의 항을 가지고 있다.

 

 

그런데 다른 DP 문제에서도 많이 적용할 수 있는 기법이지만, 이런 생각을 할 수 있다.

현재 1의 제곱수만 따져보는 경우 N = 5 케이스는 , 1² 을 포함한다면 N = 4 케이스에 항을 하나만 더 추가하는 것이다.

 

점화식으로 표현하자면 dp[현재숫자] = 1 + dp[현재숫자 - (1 * 1)] 로 나타낼 수 있는 것이다.

 

 

 

< 1, 2 의 제곱수들의 합으로 만들 때 항의 수 >

 

0

1

2

3

4 1

5 2

6 3

7 4

8 2

9 3

10 4

11 5

12 3

13 4

14 5

15 6

 

이번에는 2 도 포함하는 경우이다.

 

2 의 제곱인 4 부터 시작한다. 더 작은 수인 1, 2, 3 은 어차피 2의 제곱으로 표현할 수 없기 때문이다.

4 에서 2² 를 하나 포함하면 남은 수는 0 이 된다. (4 - 2 * 2) 0 을 표현할 수 있는 제곱수의 항 (dp[0]) 은 0 개 이므로 여기에 1 을 더한 1 이 1, 2 의 제곱수들의 합으로 만드는 항의 수이다.

기존에 1 로만 구성하여 만든 케이스 (1² + 1² + 1² + 1²) 4가지 보다 더 적은 항 (2²) 1가지 로 만들 수 있으므로 대체한다.

 

식으로 정리하자면 

 

dp[j] = min(dp[j] , dp[j - i * i]) 이 된다.

 

i 가 제곱수이고, j 는 만들고자 하는 수 가 된다.

 

 

 

작성 언어: C++

 

#include <cstdio>   // c 표준입출력
#include <algorithm> // std::min 함수
#include <limits.h> // INT_MAX 상수 (int의 최대범위)

int dp[100010] = {0, };

void solve(){
    dp[0] = 0;
    for (int i = 1; i * i <= 100000; ++i) {
        for (int j = i * i; j <= 100000; ++j) {
            int remain = j - i * i; // 제곱수를 하나 포함했을 때 나머지
            dp[j] = std::min(dp[j], 1 + dp[remain]);
        }
    }
}

int main(){
    int nNumber;
    std::fill_n(dp, sizeof(dp)/sizeof(int), INT_MAX);  // dp 배열을 큰 값으로 초기화
    scanf("%d", &nNumber);
    solve();
    printf("%d\n", dp[nNumber]);
    return 0;
}

 

 

 

 

🏆 배운 점

 

 

이전에 풀며 적용했던 풀이방법들이 떠오르며 금방 적용하게 된 문제였다.

 

많이 풀어보는 것이 실력 향상에 큰 도움이 되겠다는 생각이 든다.