[백준] 1789

수들의 합

문제

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

입력

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

출력

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

풀이

const sum = () => {
  let s = parseInt(require("fs").readFileSync("/dev/stdin").toString().trim());
  let sum = 0,
    i = 1,
    n = 0;
  while (true) {
    if (sum + i > s) break;
    sum += i;
    i++;
    n++;
  }
  console.log(n);
};

sum();

반성회

i를 1부터 1씩 늘려가면서 sum을 구한다

그러면 sum은 1 + 2 + 3 + 4 + ... 가 된다

예를 들어 s가 200이면, sum은 1 + 2 + 3 + ... 을 반복하다가 sum + i > 200 일 때 break 한다

그 시점에 sum은 1 + 2 + 3 + ... + 19일 것이고, 여기에 다음 숫자인 20을 더하는 순간 200을 넘어버리므로 그 전에 조건문을 빠져나온다

그 때까지 더한 숫자의 개수가 정답이 되는데, 그 이유는 s에서 sum을 뺀 수를 마지막 i에 더해도 ‘서로 다른 N개의 자연수' 라는 조건에 부합하기 때문에 (지금까지 오름차순으로 더해주었기 때문에 더 큰 수가 들어와도 겹치지 않는다) 그것이 최종 정답이 된다

예를 들어 s가 200이라면 i가 19일 때 빠져나왔으므로 총 숫자 개수 n은 19가 되고, 마지막 i에 s - sum = 5를 더하면 1 + 2 + 3 + ... + 17 + 18 + 24 = 200 으로 조건에 부합하기 때문이다