[코드포스] edu_round #99(div2)-B JUMPS

문제 링크 : codeforces.com/contest/1455/problem/B

Problem - B - Codeforces

 

역시 코포 문제가 직관 기르기에 좋은 것 같다. 

1+2+3+.....+ xi 의 값이 n이라면 i가 답 아니라면 최초로 (n+1)보다 큰 값이 나오는 수까지 더한 횟수(i)가 답이 된다.

이유는 음수가 두 개 이상 나오지 않는것을 공책에 써가면 직관적으로 느낌이 온다. 자명하다는 것은 알아서 증명

음수가 한 개 나온다면 그것은 +1 대신에 -1, +2 대신에 -1 , +3 대신에 -1 이런식으로 바뀔 수 있으므로 xi까지 더한 값을 sum이라 하면 sum -xi-1 ~ sum-2까지 가능하다 그래서 (n+1)보다 큰 값이 나온다면 그 값에서 어떤 수든 만들 수 있다.

 

#include <Iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <memory.h>
using namespace std;
 
 
int main() {
	int tc;
	cin >> tc;
	while (tc--) {
 
		int n;
		cin >> n;
		
		int sum = 0;
		for (int i = 1;; i++) {
			sum += i;
			if (sum == n) {
				cout << i << '\n';
				break;
			}
			else if (sum > (n + 1)) {
				cout << i << '\n';
					break;
			}
		}
	}
}