[C언어] Backjoon_Code 1193, 분수찾기

| 문제

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

1/1	1/2	1/3	1/4	1/5	...
2/1	2/2	2/3	2/4	...	...
3/1	3/2	3/3	...	...	...
4/1	4/2	...	...	...	...
5/1	...	...	...	...	...
...	...	...	...	...	...

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

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

 

| 입력

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

 

| 출력

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

 

| 예제 입력 1

14

{ 예제 출력 1

2/4

 

| 문제의 키 포인트

1. 순번의 규칙을 파악하자.

문제에서 제시한 순번을 그림도 나타내면 위와 같습니다.

2. 위 순번을 토대로 이를 i와 j 변수를 통해 정리하면

1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> 1/4 -> 2/3 ->  3/2 -> 4/1 -> 5/1 -> 4/2 -> 3/3 -> 2/4 -> 1/5 -> ...

 

i/j -> i/j+1 -> i+1/j-1 -> i+1/j -> i-1/j+1 -> i-1/j+1 -> i/j+1 -> i+1/j-1 -> i+1/j-1 -> i+1/j-1 -> i+1/j -> i-1/j+1 -> i-1/j+1 -> i-1/j+1 -> i-1/j+1 ->

 

(1) 1/1 | i/j

(2) 1/2 | i/j+1

(3) 2/1 | i+1/j-1

(4) 3/1 | i+1/j

(5) 2/2 | i-1/j+1

(6) 1/3 | i-1/j+1

(7) 1/4 | i/j+1

(8) 2/3 | i+1/j-1

(9) 3/2 | i+1/j-1

(10) 4/1 | i+1/j-1

(11) 5/1 | i+1/j

(12) 4/2 | i-1/j+1

(13) 3/3 | i-1/j+1

(14) 2/4 | i-1/j+1

(15) 1/5 | i-1/j+1

(16) 1/6 | i/j+1 

 

분모와 분자의 증감을 변수로 표현했을 때 총 반복되는 식은 4자리로 구분지을 수 있었습니다.

파랑색: i/j+1    -> 좌측으로 이동

초록색: i+1/j-1 -> 대각선 아래로 이동

주황색: i+1/j    -> 아래로 이동

빨간색: i-1/j+1 -> 대각선 위로 이동

 

위를 토대로 규칙을 조금 더 생각해보면

대각선 열이 짝수일 때 분자(i)/분모(j)는 감소하고, 홀수일 때 증가한다는 것을 알 수 있었습니다.

이를 순번과 연관지으면,

순번	대각선 열
2~3	짝수
4~6	홀수
7~10	짝수
11~15	홀수

 

| 소스코드 1(SourceCode 1)

해당 풀이는 사용자 이상한 나그네님의 풀이를 참고하였습니다.

// BOJ_1193_fraction_분수찾기
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
	int x, key = 0, i = 2, j = 1, k = 2, cnt = 2;
	
	// 순번 입력부
	scanf("%d", &x);

	// 1/1인 경우
	if (x == 1)
	{
		printf("1/1");
		return 0;
	}

	// 짝수, 홀수 대각선 판별
	while (1)
	{
		if (i <= x && i + j >= x)
		{
			if (j % 2 == 1)
			{
				key = 0; // 짝수 대각선
			}
			else
			{
				key = 1; // 홀수 대각선
			}
			break;
		}
		i = i + j + 1;
		j++;
	}

	i = 2, j = 0, k = 0;

	// 위 판별에 따른 값 출력
	while (1)
	{
		j = 1;
		for (k = i; k > 0; k--)
		{
			if (x == cnt)
			{
				printf("%d/%d", (key == 1) ? k : j, (key == 1) ? j : k);
				return 0;
			}
			j++;
			cnt++;
		}
		i++;
	}
	return 0;
}

 

| 소스코드 2(SourceCode 2)

위 코드 이외에도 다른 풀이법도 찾아보았는데요.

해당 풀이는 순번을 가지고 직접 분수를 만드는 형태의 풀이였습니다.

해당 풀이는 mokhwa님의 풀이를 참고하였습니다.

// BOJ_1193_fraction_2, 분수찾기
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int a;
	int b = 1;
	int i;

	scanf("%d", &a);

	for (i = 1; a > b; )
	{
		b += ++i;
	}

	if (i % 2 == 0)
	{
		printf("%d/%d", i - (b - a), 1 + (b - a));
	}
	else
	{
		printf("%d/%d", 1 + (b - a), i - (b - a));
	}
	return 0;
}

 

| 문제출처

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

1193번: 분수찾기