h.o. Algorithm | Java | 백준 1789 - 구현 & 그리디 - 무의미한 로직은 생략

백준 1789 풀이 알고리즘을 분석하는 글이다.

h.o. Algorithm | Java | 백준 1789 - 구현 & 그리디 - 무의미한 로직은 생략

h.o.Algorithm 로직은 존재 코드는 부재

문제

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

문제 분석

• N개의 자연수의 합이 S이다.
• N의 최댓값, 즉 최대한 많은 수를 더해 S를 구해야 한다.
• 많은 수를 더하기 위해선 1부터 사용할 수 있는 작은 자연수를 모두 더해야 한다.

알고리즘

import java.io.*;

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());
        long sum = 0;
        int N = 0;
        for(int i=1; ; i++){
            if(sum + i > S){
                break;
            }
            sum += i;
            N++;
        }
        System.out.println(N);
    }
}

알고리즘 분석

• S가 넘지 않은 최대 자연수까지 구한 후 해당 N을 출력한다.

질문 : S가 넘지 않을 때까지만 더했는데, 문제에서는 자연수의 합이 S이 되는 자연수의 수를 구하라고 했다. 문제 조건을 충족시키지 않는다.

• S가 넘지 않은 최대 자연수 N까지의 값을 더하고, N+1을 더한다. 그럼 S보다 큰 수가 된다. (현재 N+1)
• S보다 큰 수에서, S를 뺀 수를 하나 뺀다고 생각하자. 그럼 N+1개에서 한 개를 뺐으므로 자연수의 수는 다시 N이 된다. (현재 N)

하지만 실제 코드 작성시에는 마지막 두 단계를 생략했다. 알고리즘 이면에 수학적 해석이 들어가 있다. 이를 통해 로직은 존재하지만, 무의미한 작업 코드는 생략된 알고리즘이 작성됐다.