-
문제
https://www.acmicpc.net/problem/17626
17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
문제를 이해했는가?
제곱수로만 N을 만들 때, 최소한의 개수를 출력하라.
어떻게 풀 수 있지?
이 문제는 전형적인 DP이다. 왜 그럴까? 같이 생각해보자.
1. 완전 탐색
당연히 브루트포스로 풀면서, 접근을 해볼 수도 있지만 문제 속에서는 '시간을 0.5초' 로 제한을 하였다. 보통 1초에 연산을 1억번 한다고 가정 하기 때문에 가볍게 생각해보면 5천만번의 연산이 가능하다고 추론 할 수 있다. 하지만 주어진 n의 최대 값은 50,000 이기 때문에 이를 2번만 돌면서 확인해도 "25억번"의 연산이 필요하다. 즉, 시간초과가 발생한다.
2. DP
그렇다면, 이를 가능하게 하려면 "연산을 줄일 수 있는 방법" 이 필요 한 것인데 ! 그 방법을 조금 더 자세히 이야기해보면 이전에 연산한 값을 이용하면 연산을 줄일 수 있다. 그리하여, "DP" 로 풀어야 겠다는 결론을 얻을 수 있었다.
- 무엇을 기억하지?
이전에 어떤 값을 저장해서 어떤 방식으로 사용 할지 결정을 해야 하는데, 이번 문제에서 각 값에서 얻을 수 있는 최소한의 연산 횟수를 저장 하면 된다.
- 어떻게 최소 개수의 제곱수를 찾아내지?
방법은 간단하다. 자신의 자리에서 얻을 수 있는 최대의 제곱 수를 빼면 된다.
- 예시1
5에서 얻을 수 있는 최소 제곱 수의 개수는 2개이다( = 2^2 + 1^2 ).
그렇다면 이 값을 얻기 위해서는 dp[1]에 저장해놓은 1에 1개 (2^2)를 더해주면 된다.
예시 2
26에서 얻을 수 잇는 초시고 제곱 수의 개수는 2개 이다. ( = 5^2 + 1^2 )
그렇다면 이 값을 얻기 위해서는 dp[1]에 저장해놓은 1에 1(5^2)개를 더해주면 된다.
전체 코드
function solution(n) { for (let i = 2; i <= 25; i++) { let min_value = Infinity; let j = 1; // 제곱수가 자신의 값을 초과하면 // 그 제곱수로, 자신을 뺼 수 없음 => 최소한의 개수 접근 X while (Math.pow(j, 2) <= i) { min_value = Math.min(min_value, dp[i - Math.pow(j, 2)]); j += 1; } dp.push(min_value + 1); } console.log(dp[n]); } const n = 25; const dp = [0, 1]; solution(n);
'PS > 백준' 카테고리의 다른 글
[ 백준 _ 12933 ] 오리 ( 구현 - 자바스크립트 ) (0) 2021.07.09 [ 백준 _ 13019 ] A를 B로 ( 그리디 - 자바스크립트 ) (0) 2021.07.07 [백준_14247] 나무 자르기 ( 그리디 - 자바스크립트 ) (0) 2021.06.30 [ 백준_11256 ] 사탕 ( 그리디 - 자바스크립트 ) (0) 2021.06.29 [ 백준 -17609 ] 회문 ( 구현, 투포인터 - 자바스크립트 ) (3) 2021.06.29 댓글