[백준/BOJ] 1789번 수들의 합 - JAVA 자바

링크 - https://www.acmicpc.net/problem/1789

풀이 방식

그리디 알고리즘으로 최적의 해를 찾으면 되는 문제이다.
1부터 가장 작은 수들부터 더해간 뒤, 그 합이 S를 초과하면 초과한 만큼 빼주면 그 개수가 N의 최댓값이 된다.

예를 들어, S가 13이라고 가정해보자. 작은 수부터 더해가다 1+2+3+4+5=15가 S를 초과하므로 멈추고, 여기서 2만 빼주면 된다.

코드

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

public class Main {
	// 1부터 가장 작은 수들부터 더해간 뒤, 그 합이 s를 초과하면 초과한만큼만 빼주면 됨
	// ex) s = 13일 경우, 1+2+3+4+5=15 -> 여기서 2만 빼주면 됨
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long s = Long.parseLong(br.readLine());
		// s는 1보다 크고, 4,294,967,295보다 작으므로 long으로 처리함
		long num = 0, n = 0;

		for (long i = 1; ; i++) {
			// s = 1인 경우를 고려하여 i < s라는 조건은 삭제함
			num += i;
			n++;
			if (num >= s) {
				if (num > s) {
					// num이 s를 초과했다면, 초과한만큼 자연수 하나를 빼야하기 때문에 n--를 해줌
					// num == s일 경우 그대로 n값을 출력하면 됨
					n--;
				}
				break;
			}
		}

		System.out.println(n);
	}
}

개선할 점

문제의 조건을 잘 보자...!! 1의 최댓값이 4,294,967,295인 점을 고려하지 않고 s를 int로 정의했다가 런타임 에러가 발생하였다.
처음엔 풀이 방향을 잡지 못하고 다양한 방식을 생각하다 엉뚱한 방식으로 빠졌는데, 알고리즘 문제를 더 꾸준히 풀어야 할 것 같다.