[백준/C++] 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 

1

예제 출력 1 

1/1

예제 입력 2 

2

예제 출력 2 

1/2

예제 입력 3 

3

예제 출력 3 

2/1

예제 입력 4 

4

예제 출력 4 

3/1

예제 입력 5 

5

예제 출력 5 

2/2

예제 입력 6 

6

예제 출력 6 

1/3

예제 입력 7 

7

예제 출력 7 

1/4

예제 입력 8 

8

예제 출력 8 

2/3

예제 입력 9 

9

예제 출력 9 

3/2

예제 입력 10 

14

예제 출력 10 

2/4

---

1️⃣ 첫번째 풀이 : 약간 하드코딩?

 

처음에는 분수들간의 규칙을 제대로 찾지 못하여 대각선으로 움직이는 2차원 배열의 인덱스를 계산하며 문제를 풀이하였다.

시간초과가 날 줄 알았지만 X의 범위가 천만이어서 시간초과까지는 발생하지 않고 문제를 해결할 수 있었다.

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int main()
{
	int cnt = 1;
	int x = 0, y = 0;
	int X;
	bool down = true;

	cin >> X;

	while (cnt < X)
	{
		if (y == 0)
		{
			x++;
			cnt++;
			if (cnt == X) break;

			y++;
			x--;
			down = true;
		}
		else if (x == 0)
		{
			y++;
			cnt++;
			if (cnt == X) break;

			x++;
			y--;
			down = false;
		}
		else
		{
			if (down)
			{
				y++;
				x--;
			}
			else
			{
				y--;
				x++;
			}
		}
		cnt++;
	}

	cout << (y + 1) << "/" << (x + 1) << endl;

	return 0;
}

대각선으로 이동하는 x, y 인덱스와 대각선이 위쪽 방향으로 증가하는지 아랫쪽 방향으로 증가하는지를 bool down 변수로 판단하여 숫자의 흐름을 검사하는 방식으로 풀이하였다.

 

2️⃣ 두번째 풀이 : 답지 보고 배우기

 

문제를 해결했지만 분명 더 간단한 풀이가 있을것이라 생각하고 다른사람들의 코드를 공부해보았다.

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int main()
{
	int x;
	cin >> x;

	// 1. 찾고자 하는 숫자가 몇번째 대각선에 위치하는지 찾기
	int i = 0;
	while(x > 0)
	{
		i++;
		x -= i;
	}

	// 2. 대각선이 홀수번째인지 짝수번째인지 구별한 뒤,
	// 각각의 경우에 따라 x값을 반전하여 출력
	if (i % 2 == 1)
		cout << 1 - x << "/" << i + x;
	else
		cout << i + x << "/" << 1 - x;

	return 0;
}

 

처음에는 코드를 보고 전혀 무슨 흐름인지 이해하지 못했지만, 친절하게 그림을 그려 설명해주는 분들 덕에 이해할 수 있었다..

 

첫번째로는 대각선이 몇번째 대각선인지를 판별해야 했다.

그 이유는, 대각선이 늘어날때마다 스위치처럼 흐름이 위 - 아래로 변화되기 때문이다.

첫번째 대각선부터 위, 두번째는 아래, 세번째는 다시 위, 네번째는 아래 처럼 흐름이 변화하였다.

 

몇번째 대각선인지를 판별하기 위해선 구하고자 하는 숫자 x를 입력받고, 해당 x에 대각선에 위치한 숫자들의 크기만큼 개수를 빼주었다.

이때, 대각선을 보면 첫번째에는 1개의 요소, 두번째에는 2개의 요소, 3번째에는 3개의 요소,, 처럼 대각선의 개수가 늘어남에 따라 비례하는 요소 개수가 늘어남을 확인할 수 있었다.

 

따라서 while문을 돌며 x에 i++ 씩 1만큼 증가하는 i를 계속해서 빼주었고, x값이 0보다 작거나 같아지는 순간이 대각선의 위치를 나타내는 것이다.

 

두번째로는 대각선이 위로 이동하는지 아래로 이동하는지 판별하기 위해 짝수번째인지 홀수번째인지를 검사하였다.

짝수번째와 홀수번째는 서로 대칭되어 출력되기에 분모와 분자만 바꾸어 출력하면 된다.