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

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

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

17626번: Four Squares

---

- 문제 -

 

난이도 브론즈 3 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

dp 문제이다. 처음에 단순하게 생각해서 제일 가까운 제곱수들을 빼주면 될 줄 알았다. 하지만 예외가 있었고, 지금 그것을 확인해보겠다.

0은 0개이다.

1은 1*1.                    1개이다.

2는 1*1/1*1.              2개이다.

3은 1*1/1*1/1*1.         3개이다.

4는 2*2.                    1개이다.

5는 2*2/1*1               2개이다.

6은 2*2/1*1/1*1          3개이다.

7은 2*2/1*1/1*1/1*1     4개이다.

8은 2*2/2*2                2개이다.

9는 3*3                     1개이다.

얼추 패턴이 보인다.

10은 3*3/1*1              2개이다.

11은 3*3/1*1/1*1         3개이다.

12는 3*3/1*1/1*1/1*1    4개이다.라고생각했지만.

여기서 예외가 나온다. 12는 지금했던 것처럼하면 4개지만, 2*2/2*2/2*2로도 12가 나오고, 이건 3개이다. 그렇다면 결국 12일때 답은 3이 되는 것이다. 그렇다면 예외를 알았으니 패턴을 보자.

기본적으로 제곱수 자체일 때는 1이다. 그리고 그 값을 기준으로 1씩 증가하다가 예외 사항이 생기면 8이나 12처럼 값이 1이 증가하는 패턴이 아닌 다른 패턴이 나온다. 그래서 여기서 쓸 것은 i - j*j이다.

i - j*j라고해도 이해가 안될 것이다.

12로 보자. i는 현재 값 즉 12가 된다. j는 1부터 제곱했을때 i 이하인 값이다. 그렇다면 j에는 1부터 3까지 들어갈 것이다.

i - j * j. i = 12, j = 1일때 보자. 12 - 1*1 = 11. 11의 개수는 3개이다. 다음을 보자.

j가 2일때, 12 - 2*2 = 8. 8의 개수는 2이다.

j가 3일때, 12 - 3*3 = 3. 3의 개수는 3이다.

이중 제일 작은 값을 구해주면 된다. 제일 작은 값은 2이다. 마지막으로 제일 작은값에 +1을 해주면 출력값이 된다. 3이 되는 것이다.

하나만 더 예를 들어보자.

25. j는 1~5까지 올 수 있다.

j가 1일때 25 - 1*1 = 24. 24의 개수는 3이다.

j가 2일때 25 - 2*2 = 21. 21의 개수는 3이다.

j가 3일때 25 - 3*3 = 16. 16의 개수는 1이다.

j가 4일때 25 - 4*4 = 9. 9의 개수는 1이다.

j가 5일때 25 - 5*5 = 0. 0의 개수는 0이다.

최솟값은 0이고, 출력값은 +1인 1이 된다.

 

코드를 보자.

---

-풀이-

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];
		
		dp[0] = 0;
		dp[1] = 1;
		for(int i = 2; i <= n; i++) {
			//현재 구할 값의 개수는 전 값의 +1이니 전 값을 그대로 우선 가져온다.
			dp[i] = dp[i - 1];
			for(int j = 1; j * j <= i; j++) {
				//현재 들어가있는 값과, i - j * j의 값과 비교해서 작은 값을 다시 저장
				dp[i] = Math.min(dp[i], dp[i - (j * j)]);
			}
			//최솟값이 저장되었을테니 +1을 해서 마무리 해준다.
			dp[i]++;
		}
		System.out.println(dp[n]);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.