72. C++ 백준 1789번 수들의 합 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘 문제인 수 들의 합 C++ 백준 1789번 입니다.

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

 

 

N개의 자연수의 합 S가 주어질 때 N의 최대값을 묻는 문제이므로

최대한 작은 수들의 합이 S 가 되면 되겠죠.

1부터 n까지의 합은 n * (n +1)/2 입니다.

3가지의 경우가 있습니다.

1. S보다 1부터 n까지의 합이 작다면  S = n(n+1)/2 을 만족시키지 못하므로 n을 증가시킵니다.

2. S보다 1부터 n까지의 합이 S 와 같다면 n은 S를 만들기 위한 N의 최대값이 되고 

3. S보다 1부터 n까지의 합이 S보다 크다면 (n을 1씩 증가시키면서 n * (n +1)/2 을 만들었을 때)

n * (n -1)/2  이 S보다 작고, n(n+1)/2 가 S 보다 크다는 말과 같고 

첫번째 식에서 n을 더했을 때 S 보다 커지게 되므로

n보다 작고 S = n(n+1)/2 - x  를 만족하는 수 x가 지금까지의 합에 존재한다는 것을 알 수 있습니다.

즉 S가 주어질 때 N의 최대값은 n - 1개가 되죠

위 직관으로 코드를 작성해봅시다.

 

1부터 N까지의 합이 S 보다 작다면 N 을 1부터 1개씩 증가시키면서, 계속 비교하고

int N = 1;

while ( 1 ){
    sum += N;
    if (sum > S) break;
    N++;
}

 

1을 빼서 출력해주면 됩니다.

cout << N - 1;

 

아래와 같이 합의 공식을 써서 작성을 해보았더니

while ( N(N+1)/2 < S ){

시간 초과가 나서 매번 n을 두번 곱하는 연산이 아닌

처음과 같은 방법을 사용 했습니다.

 

 

수 들의 합 백준 1789번 C++ 최종 코드입니다.

#include <iostream>
using namespace std;
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    long long S, sum = 0;
    int N = 1;
    cin >> S;
    while ( 1 ){
        sum += N;
        if (sum > S) break;
        N++;
    }
    cout << N - 1;

    return 0;
}

 

제가 운영하는 오픈 카톡방입니다. 알고리즘, 코딩, 취업정보 등 자유롭게 질문, 답변 및 대화 나눠요.

https://open.kakao.com/o/guGhqGAg

알고리즘, 코딩, 개발자 취업 질문방 (비번 4321)

 

 

 수 들의 합 백준 1789번 C++ 자세한 설명이었습니다. 감사합니다.