[코딩테스트] Java_ 백준 1789번 수들의 합 (그리디 알고리즘) - Rowen Jobs

백준 1789번 수들의 합

전 접근 방식은 비슷했으나 조금 더 단순하게 생각했으면 빨리 풀었을 문제입니다.

N개의 자연수를 다 합치면 S 가 될때 주어진 S가 되기 위한 N 개의 갯수의 최댓값을 푸는 문제 입니다.

최대의 갯수이기때문에 제일 작은 값을 total 변수에 순서대로 더하고 

total 변수가 S 를 넘기 전 카운트가 곧 최댓값입니다.

---

간단 예시 풀이

200의 경우 

1 ~ 19까지 더하게 되면 190이고   19번입니다.

1 ~ 20까지 더하게 되면 210이고 넘게되는 카운트인 20입니다. 

앞서 설명드린 넘기 직전 카운트인 19개가 답입니다. 

이유를 설명 드리자면 직전 카운트인 19개 에서 그 전 카운트에 더했던 18로 돌아갑니다. 

1 + ... + 18 = 171;  18번인 상태에서 200이 될려면 29가 필요하고 

1 + ... + 18 + 29 = 200 으로 19번이 됩니다. 

 

---

수들의 합 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

51515

20972

17815

41.735%

문제

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

입력

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

출력

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

예제 입력 1 복사

200

예제 출력 1 복사

19

출처

• 문제를 만든 사람: author5
• 데이터를 추가한 사람: kangwh0617, newton08, upple1

알고리즘 분류

• 수학
• 그리디 알고리즘

 

참고 코드는 아래와 같습니다. 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
    	// 입력값 셋팅
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 더한 값 입력
        long S = Long.parseLong(st.nextToken());
        
        // 자연수 갯수 변수
        int N = 0;
        
        // 더한 값 총합 변수
        long total = 0;
		
        // 1일 경우는 반복문이 필요 없어 예외 처리
        if(S != 1){
        	// 1 + ... + 넘는값 직전 카운트
            for(long i = 0 ; i < S; i++){
            	// 총합 Sum
                total += (i + 1);
                // 총합이 주어진 값을 넣으면 break / 그렇지 않으면 자연수 갯수 변수 증감
                if(total > S){
                    break;
                }else{
                    N++;
                }
            }
        }else{
            N = 1;
        }
		// 위에 설명 드렸듯이 넘기 직전 카운트가 자연수 N의 갯수 최댓값 입니다. 
        System.out.println(N);
    }
}