백준1669 - 멍멍이 쓰다듬기

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

1669번: 멍멍이 쓰다듬기

수열을 찾아푸는 문제다. 다음과 같은 규칙이 나온다. 시작과 끝은 무조건 1로 고정이 된다. 나머지 부분은 직전 수에서 1을 증가시키거나 1을 감소시키거나 그대로 사용한다는 규칙이다. 그렇게 되면 피라미드 형식으로 가운데에서 대칭이 된다.  

 

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int n; //키 차이
	int a, b; //원숭이 키, 개 키

	cin >> a >> b;
	n = b - a; //키차이


	/*
		1 (1)
		1 1 (2)
		1 2 1 (3 4)
		1 2 2 1 (5 6)
		1 2 3 2 1 (7 9)
		1 2 3 3 2 1 (10 12)
		1 2 3 4 3 2 1 (13 16)
		1 2 3 4 4 3 2 1 (17 20)
	*/

	if (n == 0) { //키가 같은 경우
		cout << 0;
	}
	else if (n == 1 || n == 2) { //키 차이가 1인 경우
		cout << 1;
	}
	else {
		unsigned long long int start = 3; //시작일
		unsigned long long int end = 4; //끝일
		unsigned long long int len = 1; //수의 범위 길이
		unsigned long long int loop = 0; //루프가 돈 횟수
		unsigned long long int cnt = 3; //키를 늘리는 일수
		while (true) {
			if (start <= n && n <= end) { //찾는 수의 범위에 들어 있는 경우
				break; //탈출
			}
			else {
				if (loop % 2 == 1) { //직전 루프가 홀수번째 실행한 루프이면
					len++; //수가 들어있을 수 있는 범위를 증가
				}				
				start = end + 1; //시작은 직전 범위에서 1을 더한 값
				end = start + len; //끝은 다음 시작에서 수가 들어있을 수 있는 범위를 더한 것
			}
			loop++; //루프가 돈 횟수를 증가
			cnt++; //키를 늘리는 일수를 증가
		}
		cout << cnt;
	}
}