백준 1789 - 수들의 합

문제링크

• 백준 1789

문제 접근

• N의 최대값을 구하는 문제이므로 가장 작은 수부터 더해가는 방법을 택했다.
• 입력받은 S값을 넘지 않는 누적합을 구하고, 마지막에 더한 자연수가 최대개수 N과 같다.
• 예를 들어, S=57인 경우 1+2+…+10 = 55 임을 이용한다. 이 상태에서 단순히 10을 빼고 12를 더하면 57을 완성할 수 있기 때문에 56~65 범위에 해당하는 S는 언제나 최대 10개의 정수를 더하여 만들 수 있다.
• 일반화하면, 1부터 차례대로 누적합을 진행할 때 언제나 다음에 오는 수가 현재 더한 수보다 크다. 따라서, S를 넘기지 않는 누적합을 구한 후 마지막에 더한 수를 빼고 그보다 큰 수를 더하면 S를 만들 수 있고 이는 곧 마지막에 더했던 자연수가 N의 최대값이 됨을 의미한다.

의사코드(pseudo-code)

- input S
- init sum = 0, i=1
- while sum<=S do:
	- sum += i
	- i += 1
- if sum>S then:
	- i -= 1
- print "i-1"

소스코드 및 분석

전체 코드

#include <iostream>
using namespace std;

int main()
{
	unsigned int S;
	cin >> S;
	unsigned long long sum = 0;
	int i = 1;
	while (sum <= S) {
		sum += i++;
	}
	if (sum > S)
		i--;
	printf("%d\n", i-1);
}

• unsigned int 자료형을 선택한 이유는 문제에서 입력받는 S값의 범위를 포함하기 위해서이다.
• sum의 경우 누적합을 진행하다보면 S값을 초과하는 경우가 생긴다. 따라서 이를 방지하고자 더 큰 자료형 범위를 선택했다.
• while문을 빠져나올 때 i값은 기본적으로 1이 증가된 상태로 빠져나온다. 이는 누적합을 구할 때는 사용되지 않은 값이므로 출력시 i-1 을 기본적으로 해준다.