BOJ - 1789 수 들의 합

문제 링크 :https://www.acmicpc.net/problem/1789

문제 유형 : 그리디 알고리즘

문제 풀이 : 서로 다른 N개의 자연수의 합으로 S를 만들어야 한다는 문제고 그리디 알고리즘의 특성을 살려서 풀었다.

가장 핵심 아이디어는 1부터 쭉 더했을 때 어느 시점에 S를 넘어갈 것이다. 그 때를 체크해주면 된다. 

1) 1부터 계속 더해준다. ex) 1+2+3+4....

2) 그러다 S를 초과하는 경우가 발생할 때를 확인한다. ex) S = 15 , 1+2+3+4+5 (O) / 1+2+3+4+5+6 (X) 

3) 한 번 씩 더 할 때마다 count를 세주고 만약 2)와 같이 초과하는 경우가 발생 했을 때 이미 count를 한 번 한 상황이니 1을 빼주고 그 count를 출력한다. ex) 6까지 갔을 때 count = 6 but 15를 초과했기 때문에 -1 해서 결괏값은 5가 나와야 함

 

문제 코드

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let s = Number(input[0]);
let sum = 0;
let count = 0;

for(let i=1;;i++){
    sum+=i;
    count++;
    if(sum<s){
        count--;
        break;
        }
}
console.log(count);

 

 

2) GPTs 풀이 (GPTs 링크 : https://chatgpt.com/g/g-uWf5rBEwE-baegjun-algorijeum-bbusyeobbusyeo)

백준 1789번: 수들의 합

문제 설명

백준 온라인 저지의 1789번 문제 "수들의 합"은 다음과 같은 문제입니다:

서로 다른 N개의 자연수의 합이 S라고 할 때, 자연수 N의 최대값을 구하시오.

즉, 주어진 자연수 S에 대해, 합이 S가 되는 서로 다른 자연수의 최대 개수를 찾아야 합니다.

접근 방법

이 문제는 다음과 같은 접근 방법을 통해 해결할 수 있습니다:

1. 그리디 알고리즘: 자연수는 1부터 시작하여 순차적으로 더해 나가는 방식으로 접근합니다.
2. 최대 개수 찾기: 1부터 시작하여 더해 나가다가, 합이 S를 초과하는 시점에서 반복을 종료합니다.

예제

• 예를 들어, S = 15인 경우를 생각해 봅시다.
  • 1 + 2 + 3 + 4 + 5 = 15가 됩니다.
  • 이 경우, 서로 다른 자연수의 최대 개수는 5개입니다.

구현 방법

1. 자연수 더하기: 1부터 시작하여 자연수를 순차적으로 더합니다.
2. 합이 S를 초과하지 않을 때까지 반복: 합이 S를 초과하면 반복을 종료합니다.
3. 자연수의 개수 출력: 반복이 종료되었을 때의 자연수 개수를 출력합니다.

알고리즘

• i를 1부터 시작하여 더해 나갑니다.
• sum에 i를 더해가며, sum이 S보다 크지 않을 때까지 반복합니다.
• 이때, 더해진 자연수의 개수를 세어 나갑니다.

시간 복잡도

• 이 알고리즘은 O(N)의 시간 복잡도를 가집니다. 여기서 N은 더해진 자연수의 개수입니다.
• S가 매우 큰 경우에도 N은 비교적 작으므로, 시간 복잡도는 효율적입니다.

예제 코드 (JavaScript)

아래는 이 알고리즘을 구현한 JavaScript 코드입니다:

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim();
let S = BigInt(input);

let sum = BigInt(0);
let count = BigInt(0);
let i = BigInt(1);

while (sum + i <= S) {
    sum += i;
    count++;
    i++;
}

console.log(count.toString());

코드 설명

1. 입력 처리:
   • 입력 값을 받아 S로 변환합니다. 입력 값이 매우 클 수 있으므로 BigInt를 사용합니다.
2. 변수 초기화:
   • sum은 현재까지의 합을 저장합니다.
   • count는 더해진 자연수의 개수를 저장합니다.
   • i는 현재 더할 자연수를 나타냅니다.
3. 반복문:
   • sum에 i를 더해가며, sum이 S보다 작거나 같을 때까지 반복합니다.
   • 반복이 진행될 때마다 count를 증가시키고, i를 증가시킵니다.
4. 결과 출력:
   • 최종적으로 더해진 자연수의 개수인 count를 출력합니다.

결론

이 문제는 그리디 알고리즘을 사용하여 효율적으로 해결할 수 있습니다. 자연수를 1부터 차례대로 더해가면서 합이 주어진 S를 넘지 않도록 하는 방식으로, 최대 개수를 쉽게 구할 수 있습니다. 이 방법은 단순하면서도 매우 효과적입니다.