[PS 백준 - 3.4] 1789번: 수들의 합

문제 정보

백준 1789번 - 바로가기

• 난이도: 실버 5
• 알고리즘: 그리디 알고리즘

---

코멘트

가장 작은 숫자부터 더해지는게 가장 많이 더하는 방법일거라 생각하고 1부터 차례대로 더해보았더니 $\frac{n(n+1)}{2}$ 단위로 개수가 올라가는 것을 발견하였다.

$10=1+2+3+4$
$11=1+2+3+ {\color{Red}4}+5-{\color{Red}4}$
$12=1+2+ {\color{Red}3}+4+5-{\color{Red}3}$
$13=1+ {\color{Red}2}+3+4+5-{\color{Red}2}$
$14= {\color{Red}1}+2+3+4+5-{\color{Red}1}$
$15=1+2+3+4+5$

위의 예시처럼 $10\sim14$는 4개가 최대고, $15$부터는 5개가 된다. 이 사실을 이용하여 반복문을 돌려 답을 구하였다.

---

소스 코드

#include <iostream>

using namespace std;

int main() {

    unsigned long long int s;
    cin >> s;
    unsigned long long int cou = 0;
    for (unsigned int i = 0; i < 100000; i++) {
        cou += i;
        if (cou > s) {
            cout << i-1;
            break;
        }
    }

}