BOJ) 제곱수의 합

제곱수의 합

1699번: 제곱수의 합

풀이

 

푸는데 꽤나 많은 시간이 소요됐다.

처음에는 50%에서, 다음에는 99%에서 런타임 에러가 떠가지고 아리송했다.

for(int i=2; i<=n; i++) {
	for(int j=2; j*j <=i; j++) { dp[i] = dp[i] ==0 ? dp[i-j*j] +1 : Math.min(dp[i],dp[i-j*j] +1); }
}

이 코드가 처음에 작성했던 코든데, j*j가 i 이하까지 증가하니까 i-j*j에서 범위를 초과하지 않을 거라고 생각했다.

그게, 인덱스의 범위든 int 의 범위든.

하지만, 런타임 에러가 떴고 질문 게시판을 참고하니까 int의 범위 초과란다.

 

long으로 바꿔서 다시 int로 parsing을 해야하나 하다가 위의 방법을 포기하고 로직 조금 바꿨다.기존에 dp[1] =1, dp[2] = 2, dp[3] =3 을 저장해놓고, dp의 i인덱스가 0이 아닌 경우 값을 저장하는게 아니라, dp[i]에 i를 저장하고 최소값을 구하는 식으로 바꿨다.

dp[1] =1;

for(int i=2; i<=n; i++) {
	dp[i] = i;
	for(int j=2; j*j <=i; j++) { dp[i] = Math.min(dp[i], dp[i-j*j]+1); }
}

위와 같이 dp[1]에만 초기 값을 저장해주고, 2부터 증가하면서 가장 최소 조합의 수를 저장해 나간다.이 코드는 통과를 했는데, 삼항 연산자의 인덱스를 불러오는 부분에서 왜 런타임에러가 떴는지 모르겠다...

 

코드

 

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());
        br.close();
        solution(n);
    }

    private static void solution(int n) {
        int[] dp = new int[n+1];
        dp[1] =1;

        for(int i=2; i<=n; i++) {
            dp[i] = i;
            for(int j=2; j*j <=i; j++) { dp[i] = Math.min(dp[i], dp[i-j*j]+1); }
        }
        System.out.println(dp[n]);
    }
}