[백준 1789 : 실버5] 수들의 합 ( 그리디 / Java )

이번 문제는 내가 문제 이해를 잘 못해서 답을 풀지 못해 답을 보고 이해하고 나니 매우 쉬운 문제였다.

 

 

문제를 살펴보자.

 

 

문제

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

 

 

 

 

 

문제 접근 방법

 

N개의 자연수의 합 S를 만들기 위해 필요한 N의 최대값을 구해라

 

이게 무슨 소리냐면 

S가 55라고 치면 

55가 나올수 있는 방법은 

1+54이 될수 있고 

1+2+53 이 될수 있다. 하지만 이렇게 되면 

N의 값은 2또는 3이 된다.

따라서 최대값이 될수 없다.

그래서 우리가 N의 최대값을 구하려면 최대한 많은 수를 더해야 한다.

최대한 많은 수를 더하려면 우리가 할수 있는 방법은 1부터 S가 되거나 넘을때까지 값을 계속해서 더하면 된다.

 

하지만 여기서 문제가 생긴다.

S가 1부터 더한 값이랑 같을수가 있는데 더한값이 더 커진 경우가 생긴다.

 

예를 들자면 S가 50일때

1+2+3+4+5+6+7+8+9+10 을 하게 되면 N의 값은 10이 되고 10이 되면 S 값인 50을 넘어가게 된다.

그럼 총 합인 55가 50이 되려면 5를 빼주면 된다.

그렇게 되면 5를 뺐으니 N의 값은 9가 되는것이다.

 

이처럼 총합이 S보다 넘어가면 특정 수를 한개 빼게 되면 N의 값이 나오게 된다.

 

따라서 소스는 아래와 같아진다.

 

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

public class Run {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Run a = new Run();

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		long num = Long.parseLong(br.readLine());
		long sum = 0;
		int count = 0;
		while(sum<=num) {
			sum+=(++count);
		}
		int answer = sum == num ? count : (count-1);
		System.out.println(answer);
		
	}
}

 

 

느낀점

1. 자료형에 유의하며 변수를 만들자.

2. 문제가 말하는게 무엇인지 자세히 살펴보자.