1699 : 두 수의 합 - JAVA

https://www.acmicpc.net/status?user_id=kpark1003&result_id=4

 

기초적인 dp 문제이다.

다만 실버 2를 받은 이유는 증명이 어렵기 때문이라고 생각한다.

나는 손을 이용한 증명을 하였다.

dp[1] - 1
dp[2] - 1+1 = 2
dp[3] - 1+1+1 = 3
dp[4] - 2 = 4
dp[5] - 2 + 1 = 5
dp[6] - 2 + 1 + 1 = 6
dp[7] - 2 + 1 + 1 + 1 = 7
dp[8] = 2 + 2
dp[9] = 3
dp[10] = 3 + 1
dp[11] = 3 + 1 + 1
dp[12] = 3 + 1 + 1 + 1
dp[13] = 3 + 2
.
.
.

 

계속 1, 11, 111형태가 끝나고 2가 되고, 2 2개가 모이면 3이 되는 형태,
3도 이런 기조로 가다가 16이 되면 다시 4로 변하는 형태이다.

 

비교적 큰 수인 41부터 살펴보겠다.

dp[41] = 1 41개 = 2 10개와 1 1개 = 3 4개와 2 1개 1 1개 = 4 2개와 3 1개 = 5 1개와 4 1개
= 6 1개와 2 1개와 1 1개
결국은 5 1개와 4 1개더한 것이 최소, 값은 2가 된다.
42나 43 44 값을 188로 12321로 늘려봐도 이런 연산을 통해 최소값을 산출해낸다.

중요한것은 꼭 큰 제곱수를 뺀것만이 작은수를 도출해낼수 없다는 점이다.

41에서 6의 제곱을 빼면 3개가 되지만 5의 제곱을 빼면 4의 제곱을 뺄 수 있기에 2개가 되기 때문이다.

따라서 최소는 두개가 되고 정답은 두개가 되기 때문이다.

나는 이런 작업을 코드로 구현하고자 했다.

 

일단은 dp 배열에 모든 값을 전부 집어넣는다. 가장 큰 숫자를 불러와서 최솟값 결정을 하는 것 보다, 1이 n개 있음을 나타내는 형태가 더 빨랐다.

아마도 Max를 매 반복문마다 불러내고 연산하는 과정이 시간이 많이 소모됐던것 같다.

		for(int i = 1; i <= n; i++) {
			dp[i] = i;
		}

 

dp문이자 이 문제의 핵심 알고리즘이다. 

		for(int i = 2; i <= n; i++) {
			//제곱수까지 봐야함
			for(int j = 1; j * j<= i; j++) {
				dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
			}
		}

처음 반복문을 돌리고 기존 1의 갯수와 숫자에 충족하는 제곱수만큼 반복문을 추가로 돌린다. 

1을 더해준 이유는 가장 큰 수 or 기준이 되는 수가 미포함 되는 형태이기 때문이다.

41을 예로 들면

41과 40을 비교

41과 37을 비교

.. 이렇게 제곱수 만큼 뺀 값들으로 계산이 들어간다.

즉, 아까 쓴

dp[41] = 1 41개 = 2 10개와 1 1개 = 3 4개와 2 1개 1 1개 = 4 2개와 3 1개 = 5 1개와 4 1개
= 6 1개와 2 1개와 1 1개
결국은 5 1개와 4 1개더한 것이 최소, 값은 2가 된다.
42나 43 44 값을 188로 12321로 늘려봐도 이런 연산을 통해 최소값을 산출해낸다.와 같은 작업을 이 코드는 하는 것이다. 최솟값 비교와 함께!

 

이렇게 최솟값을 도출하여 답으로 쓴다.

 

소스코드

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n+1];
		for(int i = 1; i <= n; i++) {
			dp[i] = i;
		}
		for(int i = 2; i <= n; i++) {
			//제곱수까지 봐야함
			for(int j = 1; j * j<= i; j++) {
				dp[i] = Math.min(dp[i], dp[i-j*j] + 1);
			}
		}
		bw.write(String.valueOf(dp[n]));
		bw.flush();
		bw.close();
		br.close();
	}
}