[백준/BOJ] 1789. 수들의 합 (C++)

문제

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

 

풀이

int의 범위가 약 21억까지이므로, S는 long long형으로 선언한다.

 

1, 2, 3, ... 더한다. (변수 sum)

다음 수를 더했을 때 지금까지 수의 합(sum)이 입력받은 수(S)보다 크면, 직전에 더한 수를 뺀다.

직전에 더한 수(a) 뒤의 수는 모두 a보다 크므로, a 전에 더했던 수 하나를 더 뺀다.

이 시점에서 S와 sum의 차이가 더할 수 있는 마지막 자연수이다.

 

지금까지 더한 수의 합을 새로운 변수로 만들지 말고, 입력받은 수 S에서 1, 2, 3, ... 을 뺀다.

소스코드

#include <iostream>

using namespace std;

int main()
{
  int N = 0; // 더한 숫자 개수
  long long S;
  cin >> S;


  int i=1;
  while(i <= S){
    S -= i;
    i++;
    N++;
  }

  cout << N << endl;

  return 0;
}

회고

문제를 처음 읽었을 때 엄청 어려운 것 같았는데 논리를 먼저 생각해보니 어렵지 않게 풀 수 있었다.

 

while의 범위를 (i < S)로 했더니 S가 1일 경우 N이 0이 나오는 문제가 있었다.

범위의 시작과 끝을 주의하자.