[백준/BOJ] 1193번 분수찾기 (C/C++)

백준 온라인 저지(BOJ) 1193번 분수찾기
https://www.acmicpc.net/problem/1193

1193번: 분수찾기

* 사용언어 : C언어, C++

 

1. 문제

아래와 같은 배열에서 X번째 분수를 구하는 프로그램 출력
(순서 : 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → ...)

 

2. 풀이

코드가 짧아서 쉬워보일 수 있지만
실제로 풀이법을 구상하고 디버깅하는데에 시간이 꽤 들었습니다.

이와 같은 수열 문제는
① 문제에서 규칙을 찾고 ② 이를 일반화 한 뒤 ③ 코드로 구현하여 풀면 됩니다.

규칙을 찾기 위해 문제의 표를 시계방향으로 45도 기울이고 생각해보았습니다.

1번째 row 에는 분수가 1개, 2번째 row 에는 2개, ... n번째 row 에는 n개의 분수가 있습니다.
그렇다면 1부터 n번째 줄 까지는 총 n * (n + 1) / 2 개가 있습니다.
(이 공식을 모른다면 기초수학을 먼저 공부하셔야 할 것 같습니다)

입력받은 숫자 x 가 속해있는 줄을 r 이라고 하면,
x 는 1 부터 r - 1 까지의 합보다 크고, 1 부터 r 까지의 합보다 작게 됩니다.
이를 활용하여 r 에 1씩 더하면서 r 을 찾을 수 있습니다.
(sqrt 함수를 구현해서 한 번에 구할 수 있지만, 보다 직관적인 코드로 작성했습니다)

이제 분자(i), 분모(j)를 찾아 보겠습니다.
x가 속해있는 줄(r)을 구했으므로 r - 1 번째 줄 까지의 숫자의 개수(s)를 구할 수 있습니다.
그리고 x 에서 이 값(s)를 빼면 i 가 나옵니다.
(짝수줄 기준으로 분자가 1부터 증가하므로)

모든 분수에 대해 아래 공식이 성립하므로 j 도 쉽게 찾을 수 있습니다.

r = i + j + 1

i 와 j 는 짝수 줄 기준으로 계산했으니, 홀수인 경우 i 와 j 를 뒤집어 출력합니다.

 

3. 코드

#include <stdio.h>

int main() {
	int x;
	scanf("%d", &x);

	int r = 1;

	while (1) {
		if (r * (r + 1) / 2 >= x) break;
		++r;
	}

	int s = (r - 1) * r / 2;
	int i = x - s;
	int j = r + 1 - i;

	if (r % 2)
		printf("%d/%d\n", j, i);
	else
		printf("%d/%d\n", i, j);

	return 0;
}