[BOJ] 1789 수들의 합 (Java)

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

 

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

<공주님의 정원> 문제 부분집합으로 풀다가 시간초과 나서 보니 그리디,,,

어려워 그리디,, 이번주는 그리디 뿌셔야겠다싶어서 시작으로 고른 문제

N의 최댓값을 고르기 위해서는 1부터 1+2+3+4+5+... 더해가다가 S를 딱 넘은 시점에 숫자 하나만 빼주면 된다.

즉, S가 11 이라고 했을 때, 1+2+3+4+5 일 때 4를 빼주면 됨!

<제출코드>

package BOJ;

import java.util.Scanner;

public class BOJ_1789 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long s = sc.nextLong();
        long sum = 0;
        int cnt = 0;
        for(int i=1; ; i++){
            sum += i;
            cnt++;
            if(sum > s){
                System.out.println(cnt-1);
                break;
            }
        }
    }
}