티스토리 뷰

알고리즘

백준 1789 - 수들의 합

쉬엄쉬엄하자 2020. 1. 26. 17:03
728x90

문제

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

입력

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

출력

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

예제 입력 1

200

예제 출력 1

19

 

숫자 S가 들어오면 이 S를 서로 다른 가장 많은 자연수의 합으로 만들어 자연수의 개수를 구하는 문제입니다.

아주 간단하게 해결할 수 있습니다.

가장 작은 자연수 1부터 순서대로 누적합을 구하여 S가 나오도록 하면 됩니다.

 

예외로 순서대로 더하다보면 S를 넘는 경우가 있습니다. 딱 맞아 떨어지는 합을 구해야 하기 때문에

순서대로 더하다가 다음수를 더했을 때 S를 넘는다면 합을 멈추고 현재 합이 몇이든 간에 딱 맞아떨어지는 숫자 하나를 더하면 되므로 결과에 +1을 해줍니다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>

using namespace std;

long long int N, F;
int result;
char result_string[10];
int main()
{
	result = 0;
	int i = 1;
	long long int sum = 0;
	scanf("%lld", &N);
	//printf("%lld\n", N);
	while (sum < N) {
		//printf("%lld %d\n", sum, result);
		sum += i;
		if (sum == N || sum >= (N - i)) {
			result++;
			break;
		}
		result++;
		i++;
	}
	printf("%d", result);
}

 

'알고리즘' 카테고리의 다른 글

백준 2178 - 미로 탐색  (0) 2020.02.09
백준 6118번 - 숨바꼭질  (0) 2020.02.07
백준 - 1012 유기농 배추  (0) 2020.02.06
백준 2667번 - 단지번호붙이기 DFS풀이  (0) 2020.02.04
백준 1652번 - 누울 자리를 찾아라  (0) 2020.01.26
댓글