[백준, 1789번] 수들의 합 (구현, 그리디 알고리즘, Java)

 

문제설명

입력 & 출력

나의 풀이

이번 "백준 - 수들의 합"문제는 자연수의 합이 주어진 수 N을 넘지 않도록 최대한 많은 서로 다른 자연수를 선택하는 문제입니다.

 

이는 합이 N을 넘지 않으면서도 가능한 한 많이 선택하는 것이 목표이므로, 그리디 알고리즘(Greedy Algorithm)을 활용할 수 있습니다.

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기

 

 

그리디 알고리즘은 매 단계에서 최적의 선택을 반복하여 전체 문제를 해결하는 방법론입니다. 여기서는 "작은 자연수부터 차례로 더해가는 방식"이 최적의 선택이 됩니다.

 

• for문을 사용해 1부터 숫자를 더해갑니다.
• 합(sum)이 N을 초과하면 즉시 반복문을 종료합니다.
• 최종적으로 합을 초과하지 않은 마지막 숫자(result)를 반환합니다.

 

이 방식은 매번 가능한 최소 숫자를 선택하므로, 최적의 결과를 보장합니다.