문제

문제

풀이

\[\sum\_{k=1}^N k = \frac{N(N+1)}{2}\]

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

즉 주어진 S보다 작거나 같도록 하는 부등식이 성립한다.

\[{N^2 + N} \le 2S\] \[N^2 + N - 2S \le 0\]

이제 이 부등식을 만족하는 N의 범위를 찾기 위해, 먼저 해당 이차 방정식의 해를 구한다.

\[N^2 + N - 2S = 0\]

근의 공식은 중학교에서 배웠지만 기억이 나지 않는다…! 면 아래에 잘 써있음.

\[x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}\]

대충 넣어보자

\[N = \frac{-1 \pm \sqrt{1^2 - 4(1)(-2S)}}{2(1)}\]

어차피 자연수이므로 양의 근만 유효하다

\[N = \frac{-1 \pm \sqrt{1 + 8S}}{2}\]

이제 우리가 찾는건

\[\frac{N(N+1)}{2} \le S\]

이므로 얻은 값에서 내림(floor) 하여 정답을 찾아보자.

근데 컴퓨터는 생각보다 빠르다.

조건이 작으니까 그냥 작업 시키는게 더 편하다.

인간님의 시간은 귀하니까.

코드

있어보이는 수학 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long S = Long.parseLong(br.readLine());
        br.close();

        long N = (long)((-1 + Math.sqrt(1 + 8.0 * S)) / 2.0);
        if (N * (N + 1) / 2 > S) {
          N--;
        }
        System.out.println(N);
    }
}

그냥 딸깍 하면 정답 나오는 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long S = Long.parseLong(br.readLine());
        br.close();
        long acc = 0;
        int count = 0;

        for (long i = 1; ; i++) {
          if (acc + i > S) {
            break;
          }
          acc += i;
          count++;
        }
        System.out.println(count);
    }
}

이론적 최적과 실용적 최적 사이에 뭔가 뭔가!