[백준] 1699: 제곱수의 합
문제
문제 풀이
제곱수들은 주어진 자연수 N보다 작아야 하는 조건과 더불어, 현재 dp값보다 작아야 한다.
N까지의 dp값을 N을 제곱근으로 가장 길게 표현할 수 있는 11 N, 즉 N으로 초기화하였다.
이중 반복문을 사용하여서 i가 N까지 dp를 채우는 동안 j의 제곱근이 i를 초기화지 않은 조건 하에 dp[i- j*j] + 1(j를 선택한 counting) 이 현재 dp[i]값 보다 작을 경우 dp[i]로 선택한다.
코드
package DP;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class ANS1699 {
static int N;
static int[] dp;
public static void main(String[] args) throws IOException {
//선언
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(bf.readLine());
//dp선언 및 초기화
dp = new int[N+1];
dp[0] = 0;
for(int i = 1 ; i <= N; i++){
dp[i] = i;
for(int j = 1; j*j <= i ; j++){
if(dp[i- j*j]+1 < dp[i]){
dp[i] = dp[i-j*j] +1;
}
}
}
System.out.println(dp[N]);
}
}
11053 가장 긴 증가하는 수열, 11722 가장 긴 감소하는 수열 문제와 비슷한 방식으로 문제를 풀 수 있었다.
처음엔 시간초과가 나왔는데 아마도, j의 제곱을 Math.pow(j,2)로 표현했기 때문인것 같다. 이를 j*j로 수정하니 시간초과 결과가 나오지 않았다.
또한, 처음 코드 작성시 j를 i까지 검토하고, i값에서 j값을 뺀 수가 양수 일때 고려하는 방향으로 짰었는데, 이는 ArrayindexOutofBounds가 나왔다.
아직 동적계획법을 알기에 멀지만,, 그래도 조금씩 내가 작성한 코드가 맞는 걸 보면 뿌듯하구만!!
Author And Source
이 문제에 관하여([백준] 1699: 제곱수의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kdmstj/백준-1699-제곱수의-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)