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

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

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

풀이

개인적으로 브론즈문제치고 처음보면 어떻게 접근할지 고민할만한 문제다.

웬만한 좌표계에서 이동하는 점에대한 위치를 구할때 항상
방향벡터인 dx dy를 선언하는것을 추천한다. 이것만 구현하면 문제는 쉽다.

위그림대로 문제에서 지그재그로 이동하는것은 1-2-3-4-1-2-''' 순으로 움직이고, 각각의 경우의 방향벡터는 아래그림처럼 표현가능하다.

dir는 dx, dy에 쓰일 방향순서이다.. 우측(3) 하측(1) 으로이동시에는 총 1번만 이동하고 다시 방향을 틀어야하므로, bool check변수를 사용했다.

브론즈문제치고 상당히 값진 문제라고 생각된다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int X;
int dx[4] = {1, 1, -1, 0}; //좌하, 하, 우상, 우 순서로반복
int dy[4] = {-1, 0, 1, 1};

int main() {
	scanf("%d", &X);
	if (X == 1) { //예외처리해버렷음
		printf("1/1");
		return 0;
	}
	int dir = 0;
	int x = 1, y = 2; //초기값 1/2
	bool check = false;
	for (int i = 2; i < X; i++) {
		int xx = x + dx[dir];
		int yy = y + dy[dir];
		if (dir == 1 || dir == 3) check = true;
		x = xx; y = yy; //분수 갱신

		//방향을 바꾸는경우를 체크
		if ((dir == 0 && yy == 1) || (dir == 1 && check) ||
			(dir == 2 && xx == 1) || (dir == 3 && check)) {
			check = false;
			dir++;
		}
		if (dir == 4) dir = 0; //방향 순환
		//printf(">> %d %d\n", x, y);
	}
	printf("%d/%d", x, y);

	return 0;
}