티스토리 뷰
Solved.ac Class 완전정복 프로젝트
Class : 3 ~ 3 ++
링크
https://www.acmicpc.net/problem/17626
문제
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2.
자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.
입력
입력은 표준 입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.
출력
출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.
접근방법
n을 만들 수 있는 제곱수들의 최소 개수를 요구하는 문제이다. f(N)을 N을 만들 수 있는 최소 제곱수들의 개수라 정의할 때, f(11339)는 4라 할 수 있다. 해당 문제를 그리디 알고리즘으로 생각한다면, 아마 이 예제가 제일 큰 반례일 것이다. 그리디 알고리즘으로 생각했을 때는, f(11339)는 5가 나오기 때문이다. 그렇다면 어떻게 해결해야 할까? 정도의 물음을 가지고 풀이로 접근한다.
풀이
문제를 보면서, 확인해야할 포인트는 이전에 구한 최소 값을 사용할 수 있는가 이다. f(27)이란 값이 있다고 하면, 이문제는 f(25)+f(2)의 문제로 나눌 수 있다. 즉, 분할 정복이 가능한 DP 문제라는 것이다.
DP문제임을 알았다면, 최소를 구할 비교 조건을 잘 정하기만 하면된다. 특정 N이 존재할 때, N보다 작은 모든 제곱수들을 확인하며, 최소 값을 찾아나가면 된다.
코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main test =new Main();
}
public Main() {
Scanner sc = new Scanner(System.in);
int num =sc.nextInt();
System.out.println(solution(num));
}
private int solution(int num) {
int[] arr = new int[50001];
arr[0]=0;
//i를 만들 수 있는 제곱의 최소갯수 ?
for (int i = 1 ; i <= num;i++){
arr[i] = i;
for (int j = 0; j*j <= i ;j++){
//모든 경우의 수 계산다 해봄
arr[i] = Math.min(arr[i],1+arr[i-j*j]);
}
}
return arr[num];
}
}
결과
포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.
더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.
읽어주셔서 감사합니다.
'공부 > 코딩 테스트 준비' 카테고리의 다른 글
[백준] 1992 - 쿼드 트리 JAVA (0) | 2021.09.25 |
---|---|
[백준] 1927 - 최소 힙 JAVA (0) | 2021.09.24 |
[백준] 2579 - 계단 오르기 JAVA (0) | 2021.09.22 |
[백준] 9375 - 패션왕 신해빈 JAVA (0) | 2021.09.21 |
[백준] 11279 - 최대힙 (0) | 2021.09.20 |
- Total
- Today
- Yesterday
- 파이썬
- DP
- Database
- 코딩테스트
- 실패일기
- JNDI연동
- BFS
- looker instance 접속
- 하루 회고
- 그래프 탐색
- 아기상어미워
- Python
- 재귀
- 자바
- looker core
- 프로그래머스 문제정복
- 백준
- db
- Spring
- 프로그래머스
- value annotation
- 유클리드-호제법
- dml
- 카카오
- 브루트포스
- 플루이드 와샬
- java
- 아기상어나쁜상어
- DFS
- 9019
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |