Easy is Perfect

[백준] 1789번 C/C++ 풀이 _ 수들의 합

  • melonicedlatte
  • Aug 31, 2018


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

수들의 합 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB60382319190942.291%

문제

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

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

출력

첫째 줄에 자연수 N의 최대값을 출력한다.

예제 입력 1 

200

예제 출력 1 

19

출처

알고리즘 분류

풀이

문제 풀이 방법은 다음과 같습니다. 
먼저, 벡터에 1을 넣어주고, S에서 1을 제거해줍니다.

그리고 벡터에 가장 마지막 원소 * 2 + 3 <= S를 만족하면 (마지막 원소보다 +1인 원소를 만들기 위한 조건)
S에서 가장 마지막 원소에 있는 수 + 1을 한 수를 빼주고, 벡터에 추가해줍니다. 

항상, 벡터의 마지막 원소 + 1을 해줌으로서 숫자들 중 최소의 값을 취합니다. 
이와 같은 과정을 반복하면 정답을 구할 수 있습니다. 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int main(void) {
    ios::sync_with_stdio(false);
    LL S, N = 0;
    cin >> S;
    vector<LL> use_vec;
    use_vec.push_back(1); S--;
    if (S == 1) cout << 1, exit(0);
    // 1 씩 증가시키면서 N 에서 뺀다.  
    while (S) {
        if (use_vec.back() * 2 + 3 <= S){
            LL new_num = use_vec.back() + 1;
            use_vec.push_back(new_num);
            S -= new_num;
        }
        else {
            use_vec.push_back(S);
            break;
        }
    } 
    cout << use_vec.size();
    return 0;
}
cs



Search