본문 바로가기
Algorithm/Baekjoon

1789_수들의 합

by 모너아링 2023. 3. 2.

▶실버1

 

문제

 

풀이

서로 다른 N개의 자연수의 합이 S라고 할 때, N의 값이 최대가 되기 위해서는 1부터 빼본다.

S에서 1을 빼고, 2를 빼고, 3을 빼고 ... 계속 진행하다가 뺀 결과값이 이미 뺀 값이나 빼고 있는 값이라면 반복문을 종료하고 답을 낸다.

ex)

20 - 1

19 - 2

17 - 3

14 - 4

10 - 5 = 5 (뺀 결과값이 현재 빼고 있는 값이므로 종료)

=> 20 = 1 + 2 + 3 + 4 + 10 (5개)

※ s값의 최댓값이 매우 크기 때문에 s가 int 형이 아닌 long long 형이어야 한다. 이거 때문에 에러났음...

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;

int main(void) {
	ios::sync_with_stdio(NULL);
	cin.tie(0); cout.tie(0);

	long long s;
	cin >> s;

	//주어진 값
	long long now = s;
    //뺄 값
	long long cnt = 1;
    //N의 최댓값
	int ans = 0;
	while (1) {
		if (now - cnt <= cnt) {
			ans++;
			break;
		}
		now -= cnt;
		cnt++;
		ans++;
	}
	cout << ans << endl;
}

'Algorithm > Baekjoon' 카테고리의 다른 글

1213_팰린드롬 만들기  (0) 2023.03.05
1965_상자넣기  (0) 2023.03.03
1911_흙길 보수하기  (0) 2023.02.28
3190_뱀  (0) 2023.02.10
1874_스택 수열  (0) 2023.02.08