[BOJ] 1699. 제곱수의 합(DP, knapsack)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

가방 문제와 유사하다.

먼저 dp[N}은 

N을 제곱수들의 합으로 표현할 때 그 항의 최소개수를 의미한다.

1부터 만들 수 있는 최소 제곱수 항을 살펴보자.

1 : 1    (1개)

2 : 1, 1    (2개)

3 : 1, 1, 1    (3개)

4 : 2    (1개)

5 : 2, 1    (2개)

6 : 2, 1, 1    (3개)   

7 : 2, 1, 1, 1    (4개)

8 : 2, 2    (2개)

9 : 3    (1개)

10 : 3, 1    (2개)

11 : 3, 1, 1    (3개)

...

10을 예로 들어보면,

10은 (3, 1)이 항의 최소 개수가 되지만, 

(2, 2, 1, 1), (2, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 1, 1, 1, 1) 로 나타낼 수도 있다.

10의 제곱수들 중 가장 큰 항이 

1이라면, 10의 항의 최소 개수는 dp[9] + 1 = 2이 된다.

2라면, 10의 항의 최소 개수는 dp[6] + 1 = 4가 된다.

3이라면, 10의 항의 최소 개수는 dp[1] + 1 = 2가 된다.

즉, 10의 제곱근인 3까지의 숫자들(1, 2, 3)이 가장 큰 항일 경우,

항의 최소 개수가 가장 적은 항을 선택한다.

가방 문제에 적용해보면,

10kg을 담을 수 있는 가방이 있는데,

10의 제곱근인 3이하 수들의 제곱인 무게를 가진 물건이 여러개 있다. (1kg, 4kg, 9kg 의 물건이 여러개 있는 것이다)

10kg를 딱 맞춰서 물건을 넣을 것인데, 가장 적개 담을 수 있는 물건의 개수를 구하여라.

라는 문제와 같다고 보면 되겠다.

그러면 9kg 물건과 1kg 물건을 담는게 최적의 해일 것이다.

이해가 잘 되었길 바라며..

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <cstdio> int min(int p, int q) { return p > q ? q : p; }   int DP[100001];   int main(void) {     int n, i, j;     // freopen("input.txt", "rt", stdin);     scanf("%d", &n);     for (i = 1; i <= n; i++) {         DP[i] = i;         for (j = 1; j * j <= i; j++) {             DP[i] = min(DP[i], DP[i - j * j] + 1);         }     }          printf("%d\n", DP[n]);       return 0; } Colored by Color Scripter

cs