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

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

 

 

처음에는 문제를 이해하지 못했었는데 지그재그로 이해하기보다는 대각선으로 보는게 이해하기 쉽다. 몇번째 대각선에 속해있는 분수인지 구하고 짝수번째 대각선이면 위에서 아래로 가고 홀수번째 대각선이면 아래에서 위로 가기때문에 몇번째 분수인지만 알면 분모와 분자를 구해서 출력해주면 된다.

 

 

정답코드

#include "iostream"

using namespace std;

int main()
{
	// d: 현재 대각선 번호 , cnt : 분수의 총 개수
	int x, d = 1, cnt = 0;

	cin >> x;

	//대각선에 속하는 개수까지 증가시켜줌
	while (cnt+d < x)
	{
		cnt += d;
		d++;
	}

	//순서-지금까지의 분수 개수 = 위치
	int idx = x - cnt;
	int answer_x, answer_y;				//분자, 분모

	//짝수이면 아래 홀수이면 위로 감
	if (d % 2 == 0)
	{
		answer_x = idx;
		answer_y = d - idx + 1;

	}
	else
	{
		answer_x = d - idx + 1;
		answer_y = idx;
	}

	cout << answer_x << "/" << answer_y << endl;

	return 0;
}