[boj] (s5) 1789 수들의 합 (미완)

1519 단어 bojboj

왜 채점이 안되지..

✅ 그리디

문제

링크

풀이

서로 다른 N개의 수로 S를 만드는 방법 중 N이 최대가 되는 방법은,

S가 11이라고 하면,

1 + 2 + 3 + 4 =10이고, 1 + 2 + 3 + 4 + 5 = 는 15이기 때문에,

1 + 2 + 3 + 5 =11로 즉 4이다.

N이 최대여야 하기 때문에, 낮은 수부터 더해가며, 더한 값들이 S를 넘기기 직전에, 마지막으로 더하는 수를 조정하면 S를 만들 수 있다.

int로 계속 사용해서 오답이라구 나왔었는데 long long type으로 변경해주니 바로 해결할 수 있었다.
혹시 정답이 맞는데 틀리다고 계속 나온다면 type을 의심해보자.

코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;

    int ans = 0;
    long long sum = 0;

    for (long long i = 1; sum < n; i++)
    {
        if (sum + i <= n)
        {
            sum += i;
            ans++;
        }
        if (sum + i > n)
        {
            cout << ans << '\n';
            break;
        }
    }
}

좋은 웹페이지 즐겨찾기