[C++] 백준 1193번 분수찾기

수학 문제입니다.

n번째 위치에 올 분수를 출력하는 문제입니다.
1/1부터 지그재그 모양으로 움직입니다.

대각선으로 보았을 때
첫번째 줄 1/1 은 합이 2입니다.
2번째 줄은 합이 3입니다.
3번째 줄은 합이 4입니다.
.....

대각선이 하나씩 증가할 때마다 합이 1씩 증가합니다.
이를 이용하기 위해 대각선으로 잘라줍니다.

n과 1을 비교하고
n과 1+2를 비교하고
n과 1+2+3을 비교하고
.....

숫자를 1씩 증가한 후 더하면서 n과 비교하고 작아질때의 순서를 찾습니다.
(1씩 증가하는 이유는 대각선 모양을 보면 1 - 2 - 3 - 4 - 5 처럼 1씩 증가하는 모습을 볼 수 있다.)

14의 경우 1+2+3+4+5 = 15가 되었을 때 확인을 할 수 있습니다.
여기서 5번째 대각선이라는 것을 확인할 수 있고 합이 6을 만드는 분수라는 것을 알 수 있습니다.

이때 지그재그가 위에서 내려오는지 밑에서 올라가는지 알기위해 
대각선이 짝수의 경우 위에서 내려오고, 홀수의 경우 밑에서 올라갑니다.

나머지 연산을 통해서 짝수인지, 홀수인지 파악한 후
int a, b를 정의한 후
a는 0
b는 k + 1 (k는 대각선 위치)
을 해주고 

for문을 돌려서
a += 1;
b -= 1;
을 해주면서 위치를 찾을 수 있습니다.

 

#include <iostream>
using namespace std;

int main(int argc, char *argv[])
{
	int n;

	cin >> n;

	int k = 1;
	int num = 0;

	while (1) {
		num += k;
		if (n <= num) {
			break;
		}
		++k;
	}

	int a;
	int b;
	if (k % 2) {
		a = k + 1;
		b = 0;
		for (int i = 1; i <= n - num + k; ++i) {
			a -= 1;
			b += 1;
		}
	}
	else {
		a = 0;
		b = k + 1;
		for (int i = 1; i <= n - num + k; ++i) {
			a += 1;
			b -= 1;
		}
	}
	cout << a << "/" << b << endl;

	return 0;
}