[BOJ/백준] 1699 제곱수의 합

● [문제번호 1699] 제곱수의 합

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

1699번: 제곱수의 합

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

● 풀이 과정

: 처음에는 주어진 수(N)에서

(int)sqrt(N)의 제곱을 빼는 횟수를 최소 항의 수라고 생각했다.

 

12로 예를 들면

12 - (3^2)

3 - (1^2)

2 - (1^2)

1 - (1^2)

로 총 4개의 항이라고 생각했다.

12 = 3^2 + 1^2 + 1^2 + 1^2

 

하지만 결과는 '틀렸습니다' 이었다.

무엇이 문제일 지 찾아보니

12는 2^2 + 2^2 + 2^2 으로 최소의 항의 수는 3이었다.

 

그래서 DP를 이용하여 이미 구해진 값들을 이용하여 구할 수 밖에 없었다.

 

색상별 위치에 주목해주세요!

 

색상별로 짝을 지어 확인하면 어떤 원리로 이어지는 지 알아낼 수 있다.

 

앞부분은 앞서 구한 값을 가져오고

j^2 가 추가되는 값으로 뒤에 붙여진다.

 

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ index를 만드는데 제곱수 항의 최소 갯수

 

2. 점화식 찾기

→ 애매하지만 dp[index] = min(dp[index], dp[index - num * num] + 1)

 

3. 초기값 정하기

→ 1^2로만 이루어진 경우를 생각하여,

dp[index] = 1

(0 ≤ index ≤ N)

 

 

● 주의 할 것

: 반례로

12, 27 등이 있다.

 

 

● 참고 할 것

: 반례

https://mtoc.tistory.com/38

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// dp : index의 제곱수 항의 최소 개수
int dp[100001];
int N;

// 다이나믹 프로그래밍
void cnt()
{
    // 1^2 로만 이루어진 제곱수으로 채우기
    for(int i = 0; i <= N; i++)
        dp[i] = i;
    
    // 4부터 1^2 이 아닌 제곱수이 들어감
    // (꼭 4부터 시작 안해도 됨)
    for(int i = 4; i <= N; i++)
    {
        // 제곱수의 항을 선택
        for(int j = 2; j <= (int)sqrt(i); j++)
        {
            int jj = j * j;
            
            // 기존 항의 수 보다 더 적은 항의 수 저장
            dp[i] = min(dp[i], dp[i - jj] + 1);
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    cnt();
    
    cout << dp[N];
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [400 - 다이나믹 프로그래밍 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1463	1로 만들기	https://pirateturtle.tistory.com/199
2	11726	2×n 타일링	https://pirateturtle.tistory.com/200
3	11727	2×n 타일링 2	https://pirateturtle.tistory.com/201
4	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/202
5	11052	카드 구매하기	https://pirateturtle.tistory.com/203
6	16194	카드 구매하기 2	https://pirateturtle.tistory.com/204
7	15990	1, 2, 3 더하기 5	https://pirateturtle.tistory.com/205
8	10844	쉬운 계단 수	https://pirateturtle.tistory.com/206
9	2193	이친수	https://pirateturtle.tistory.com/207
10	11053	가장 긴 증가하는 부분 수열	https://pirateturtle.tistory.com/208
11	14002	가장 긴 증가하는 부분 수열 4	https://pirateturtle.tistory.com/209
12	1912	연속합	https://pirateturtle.tistory.com/210
13	1699	제곱수의 합	https://pirateturtle.tistory.com/211
14	2225	합분해	https://pirateturtle.tistory.com/212