1789번 수들의 합 (java)

 그리디 알고리즘

 

 ex) N = 200

 199 1

 197 2 1

 194 3 2 1

 190 4 3 2 1

 195 5 4 3 2 1

 이런식으로 빼나가면 된다.

 

 ps) S가 1일 경우 N이 1이 되기 때문에 이 경우를 생각해야한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        long N = Long.parseLong(br.readLine());
        
        solved(N);
    }
    
    static void solved(long N) {
        long cnt = 1;
        
        if(cnt==N) {
            System.out.println(cnt);
            return;
        }
        
        while(N>=cnt) {
            N-=cnt;
            cnt++;
        }
        
        System.out.println(cnt-1);
    }
}