백준 17626번 ☆

문제

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

17626번: Four Squares

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main17626 {

	static int n;
	static List<Integer> square = new ArrayList<Integer>();
	static boolean[] visit;
	static int count;
	static int min = Integer.MAX_VALUE;
	
	public static void sumSquare(int cnt) {
	
		int max = 0;
		int temp = 0;
		
		if (cnt == 1) {
			square.add(1);
			if (min > square.size()) {
				min = square.size();
			}
			
		} else {
			for (int i=1; i<cnt; i++) {
				if (i*i<=n) {
					if (max<i*i) {
						max = i*i;
					}
				}
			}
			
			square.add(max);
			temp = cnt-max;
			sumSquare(temp);
		}
	}
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		visit = new boolean[n];
		
		sc.close();
		
		sumSquare((int)Math.sqrt(n));
		System.out.println(min);
	}
}

import java.util.Scanner;

public class Main17626_1 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		int[] dp = new int[n+1];
		dp[1] = 1;
		
		for (int i=2; i<=n; i++) {
			int min = Integer.MAX_VALUE;
			
			for (int j=1; j*j<=i; j++) {
				int temp = i-j*j;
				min = Math.min(min, dp[temp]);
			}
			
			dp[i] = min + 1;
		}
		
		System.out.println(dp[n]);
	}
}

1. 멘탈까지 싹싹 털린 문제다.

 

2. 완전탐색을 가장한 dp문제라고 구글링을 통해 알게됐다. 물론 완전 탐색으로도 풀기는 가능하다 다만 코드가 난잡해지고 본 문제에서는 최대 4가지의 경우의수를 추릴 수 있기에 가능한 부분이다. 좀 더 근본적인 문제해결 방식은 아니다.

 

3. 결론은 고등학교때 한창 공부하고 문제를 풀었던 수열문제 처럼 수열의 패턴을 찾는 문제였다. 그때 당시엔 꽤나 자신있는 부분이었는데 10년도 넘는 시간이 지나버리니 그 감각이나 풀었던 방식들을 전혀 생각이나지 않는다.

 

4. 첫번째 코드는 입력된 수 n의 제곱근까지 i를 증가시키며 n에 가장 근접한 i^2를 max에 대입하고 n과  max의 차를 매개변수로 재귀함수를 호출하는 방법이다. 다만 문제에서 요하는 답에 부합되지 않는 반례들이 존재했고, 해당 부분을 구현하기 위해 다시 List에 넣어서 size를 비교하는 방법으로 해결하려했다. 하지만 재귀를 통해 값을 더하기 때문에 max의 제곱근 보다 1적은 수를 찾아 다시 로직을 진행하기엔 첫번째 코드와 같은 방식이 적절하지 않았다. 또한 모든 경우의 수를 또 같은 방식으로 찾아야 하기에 시간초과가 발생했을 것이다.

 

5. 두번째 코드는 n만큼의 배열을 생성 후 dp[2]부터 반복문을 통해 값을 저장하고 이전 값을 이용해 현재 값을 구하는 방식이다. 작은 부분부터 하나씩 맞춰가기에 dp라고 부른다.(사실 dp개념에 대해 완전히 이해하진 못했다 //개념참고:https://propercoding.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-Dynamic-Programming)

수열의 패턴을 찾았다고해도 두번째 코드의 2중 for문처럼 구성하는 것에 많은 시간을 소비했을것 같다. 추후에 꼭 다시 풀어보도록 하자.

 

6. 두번째 코드 출처 및 참고: https://steady-coding.tistory.com/18

[BOJ] 백준 17626번 : Four Squares (JAVA)