백준 17626번: Four Squares with Java

Four Squares 다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

512 MB

30933

13550

10650

43.797%

문제

라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52.

자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.

출력

출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.

예제 입력 1 복사

25

예제 출력 1 복사

1

예제 입력 2 복사

26

예제 출력 2 복사

2

예제 입력 3 복사

11339

예제 출력 3 복사

3

예제 입력 4 복사

34567

예제 출력 4 복사

4

 

 

 

---

 

<어이, 거기 자네ㅡ.. 포기하는 게 어때?>

<무슨 소리야..크윽... 이건 나를 위한 싸움이 아냐ㅡ 모두,, 모두를 위한 싸움이라구!>

 

?? 미침

아마 문제 보고 충격 받고 저래 써놓은 듯;; ㅈ 뭔 모두를 위한 싸움임 제정신이 아님

 

아

아

아

아아

아아아아ㅏㅇ아아

 

라그랑주가 증명했대..... 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 .... 세븐틴세븐티에...어? 어? 어? 난 암산의 명수들은 못하겠다. n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오. 하하

 

뭐야 글이 왜 싹 날아감 진심 열심히 썼는데 진자 억울하다 세상이 날 억까한다 

 

의지를 잃고 누워있다가 다시 쓰기 시작...

암튼 다시 요약해서 써보자면 첨엔 숫자를 반으로 나눠서 제곱을 일일히 계산할까 했다는 글을 썼고 주어진 초가 0.5초라는 걸 보고 그게 아니라 규칙을 찾는 건가? 라는 생각을 했다고 썼고 1 2 3 4 5 6 7 8 9를 쪼개보면서 규칙을 찾았다는 글을 썼었습니다 123456789 열심히 계산해서 줄줄 썼는데 개 억 울 해;;; 물론 어려운 건 아니지만요? 억울해 그래도.

 

그래서 규칙을 개 열심히 찾았...아니 열심히 노려봤다고';;;

1 4 9가 지금 제곱수자나여 그래서 아아니 이거 숫자를 다시 써야겠네

1 -> 1

2 -> 2(1 + 1)

3 -> 3(1 + 1 + 1)

4 -> 1(2 * 2)

5 -> 2(2 * 2 + 1)

6 -> 3(2 * 2 + 1 + 1)

7 -> 4(2 * 2 + 1 + 1 + 1)

8 -> 2(2 * 2 + 2 * 2)

9 -> 1(3 * 3)

10 -> 2

11 -> 3

 

볼드 처리한 게 제곱수! 첨엔 123123421? 진짜 이게 뭔 규칙임? 아무래도 아닌 듯...ㅎ 하고 튈라고 했다 근데 암만 봐도 규칙으로 풀어야 할 것 같음...

이게 8이 되는 순간(제일 가까이 있는 제곱수 4의 두 배가 되는 순간....!)  2가 되잖아...요...... 4 + 4가 되니까.... 그니까 그 전 숫자들이 영향을 미치는거지요.... 

암튼 요러다가 이상한 코드 좀 뽑다가(이거 다 날아가서 뭐 올릴 수가 없네요..?ㅎ 어차피 똥코드니 PASS..) 결국 구글링해서 좀 힌트를 (많이) 얻었었다... dp(다이나믹 프로그래밍).... 배웠던 기억이 나는데 희미하다 ㅎ

 

* dp[i] 점화식

dp[i] = min(dp[i - j^2] + 1)

이것두... 검색으로 찾은 거다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BJ_17626 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
        // dp 배열
        int[] dp = new int[n + 1];	// 1부터 시작해야하니까 사이즈는 + 1 하기
        dp[0] = 0;	// 0에는 0 넣어주기
        
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // 최악의 개수로 설정 1만 계속 더하기
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);	// 최악 개수랑 점화식이랑 비교해서 작은 걸로 넣음
            }
        }
        
        System.out.println(dp[n]);
	}
}

 

0에는 0 넣어주고 1부터는 최악의 상황 가정(1로만 더해야 할 떄...)해서 넣어주고 점화식이랑 비교해서 작은 걸로 dp[i]에 넣어준다.

점화식! 

저건 i = 8이라고 가정했을 때 j * j가 8 이하일 때만 반복한다(i보다 작은 제곱...!!!) 8이면 2까지만 돌겠쥬 1부터 해서 dp[7] + 1 = 5 나오고 dp[4] + 1 = 2 해서 2

 

근데 이 점화식은 어떻게 나온거니 

i를 고른다. 글고 가장 큰 제곱수 j^2를 고릅니다. 그러면 남은 부분은 i - j^2가 됩니다... 지금 근데 우리는 쪼개기 숫자 개수를 찾구 있잖아요? dp 배열을 만들어서 쪼개기 숫자 가장 작은 걸 저장합니다 dp[i - j^2] 여기에 1을 더하는 이유는 j^2개수도 더해야하기 때문입니다!

 

문제 쪼개서 풀고 예전 내용도 기억해야 한다는 다이나믹 프로그래밍이었습니다...

 

아 맞았습니다 안 올렸다