[c++][Greedy] 백준 1789번 문제 풀이

※ 문제의 S를 N으로 두고 풀었기 때문에 헷갈리지 않게 조심해주세요.

 

풀이

:

단순한 그리디 문제이다.

가장 많은 숫자를 더해서 N을 완성 시켜야 하므로, 작은 수부터 차례로 1,2,3,4,.....,k 까지 쭈욱 더한다.

1~k까지 더한 값을 N에서 뺐을 때 0보다 크고 N보다 같거나 작은 수가 나온다면 정답은 k이다.

 

예를 들어보자.

100 = (1+2+.....+13) + 9 .

9는 1~N 사이 값이므로 정답은 13이다.

 

좀 더 자세히 설명 해보자면 9는 이미 1~13 안에 들어있기 때문에 이렇게 바꿔줘야 한다.

100 = (1+2+.....12) + (13+9) = (1+2+.....12) + 22

따라서 갯수(k)는 13이다.

 

 

Coding

 

#include <iostream>

using namespace std;

long long int sum_one_until_a(long long int a){
    long long int sum = a * (a+1) / 2;

    return sum;
}

int main( int args , char**argv){

    long long int N;
    long long int answer;

    cin >> N;
    
    
    for(long long int i = 1 ; i <= N ; ++i){
        if(N - sum_one_until_a(i) <= i){
            answer = i;
            break;
        }
    }
    
    cout << answer;
}

 

조심해야 하는 부분은 N이 4,000,000,000 까지 입력 될 수 있기 때문에 long long int를 써 줘야 한다.

 

백준 1789번 문제

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