[백준 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)가 주어진다.

출력

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

나의 풀이

#include <stdio.h>

int main(void) {

	int n, i = 1, j, k, cnt = 0; //i : 대각선 증가 카운터, j : 분자, k : 분모
	scanf("%d", &n);

	while (1) {
		int flag = 0;
		j = 0, k = 0;
		if (i % 2 == 0) {
			for (int a = 1; a <= i; a++) {
				j = a;
				k = i - a + 1;
				cnt++;
				if (cnt == n) {
					flag = 1;
					break;
				}
			}
		}
		else {
			for (int a = 1; a <= i; a++) {
				j = i - a + 1;
				k = a;
				cnt++;
				if (cnt == n) {
					flag = 1;
					break;
				}
			}
		}
		i++;
		if (flag == 1) break;
	}

	printf("%d/%d", j, k);
	return 0;
}

문제의 지그재그 순서라 함은 다음과 같다. 

분자는 1, 1, 2, 3, 2, 1, 1, 2, 3, 4, 5, 4, ...

분모는 1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 2, ... 순서로 바뀌는 것을 볼 수 있다. 

따라서,

대각선마다 번호를 붙이고 이를 i에 대입했을 때 

i가 증가될 때마다 분자와 분모 수열의 순서를 바꿔주면 된다. 

for문이 끝날 때마다 flag를 교체해주는 방법도 있고,

i%2 연산을 통해 비교하는 방법도 있다. 

분자와 분모를 바꿔줄 때마다 카운터변수를 하나씩 증가시켜주고, 

카운터변수가 n과 같은 값이 되었을 때 분자와 분모를 출력해주면 된다.

 

(풀어보기 : https://www.acmicpc.net/problem/1193)