[코딩테스트] 백준(BAEKJOON) - 제곱수의 합(Java, 1699번)

안녕하세요.

 

이 문제는 풀지 못해 풀이를 보고 다시 풀었습니다.

 

풀고나니 생각보다 간단해 허망하네요~

 

그래도 더욱노력해 다음에는 이것보다 어려운 문제도 맞아보겠습니다.

그럼 문제 만나보시죠~

 

https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

제곱수로 이루어진 숫자들의 합중에 최소항의 갯수를 구하는 문제입니다.

 

그럼 제가 작성한 코드와 함께 간단한 설명을 남겨놓겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			Scanner sc=new Scanner(System.in);
			int number=sc.nextInt();
			int[] dp=new int[number+1];
			
			for(int i=1;i<=number;i++)
			{
				dp[i]=i;
				
				for(int j=1;j*j<=i;j++)
				{
					if(j*j==i)
						dp[i]=1;
					else if(i-j*j>0)
						dp[i]=Math.min(dp[i], dp[i-j*j]+1);
				}
							
			}
			System.out.println(dp[number]);		
	}

}

① dp[i]=i => i의 구성이 1^2으로만 이루어졌을, 즉 최고 항이 길었을 경우의 항 갯수를 먼저 부여합니다.

② 제곱수가 i보다 클 수 는 없겠죠? 그렇기에 탐색하기 전에 i의 제곱보다 작거나 같다는 조건을 부여후 반복문을 실행하겠습니다.

③ 첫 번째 if문 j*j=1일 경우입니다. 이때는 항이 1개입니다. 예를들어 9라면 9=3^2, 16이라면 4^2이렇게 말이죠~

④ 앞서 말한 경우의 수를 제외한 경우입니다. 왜 else if(i-j*j)를 했냐 하실 수도 있는데 제곱되는 반복문을 줄이기 전에 사용했던 코드를 그대로 사용하다보니 남아있네요ㅠㅠ 아마 else로 바로 사용하셔도 무방할 듯 합니다.

⑤ dp[i]=Math.min(dp[i],dp[i-j&j]+1) 부분입니다.

    최소항의 갯수를 구하기에 Math.min을 사용합니다. 다음은 dp[i]즉 최악의 숫자에서 더욱 낮은 숫자를 찾아갑니다. 그리고 dp[i-j*j]를 해서 i에서 특정 제곱수를 빼고 최소값을 갖고 있는 dp[i-j*j]의 값에 j*j 즉 항의 갯수 1개를 더하며 최소값인지 비교합니다.

 

이해가 되셨을까요?

오늘은 간단하게 마무리하겠습니다.

 

감사합니다. :D