[Baekjoon] 1193번: 분수찾기

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

1193번: 분수찾기

 

직전의 포스트와 마찬가지로, 이번 문제도 규칙성을 찾으면 쉽게 해결 가능한 문제이다. 본인은 처음 이 문제를 풀 때 너무 단순하게 생각해서 실제로 지그재그로 움직여서 구하는 코드를 짰었는데, 실행 시간이 생각보다 길게 나와서 다른 사람의 코드를 분석해보다가 깨달음을 얻고 눈물을 흘려버리고 말았다.

 

---

 

문제 해결 과정

착안

1. 실제로 지그재그로 움직여서 구한다(분자 또는 분모가 1이 될 때 방향을 전환하는 원리).
2. 아래와 같이 분수들을 그룹화 하고, 각 그룹의 규칙성을 찾아 해결한다(아래 그림 참고).

그림과 같이 분수들을 묶으면, \(i\)번째 그룹에 해당하는 분수들의 (분자) + (분모) \(= i + 1\), \(i\)번째 그룹에 속하는 분수의 개수 \(= i\)라는 두 가지의 규칙성을 찾을 수 있다.

 

구현

방법 1) 시간 복잡도가 더 높은(\(= O(n)\)) 방법이기는 하나, 규칙성을 찾지 못한 나 같은 사람이 문제를 해결할 수 있는 방법이다. increment 라는 변수를 이용해 분자와 분모의 증감을 컨트롤할 수 있다. 분자나 분모가 1일 때 증감 방향이 바뀌는 조건을 달아주는 것이 관건이며 특히 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → 1/3 → 1/4 → ... 와 같이 증감 방향이 바뀌기 전, 분모(또는 분자)만 1 증가하는 상황을 처리해주면 문제를 쉽게 해결할 수 있다(아래 코드 반복문 내의 첫 조건문 2개에 해당).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int main()
{
	int num = 1, denom = 1, increment = -1, n;
	cin >> n;

	while (n > 1)
	{
		if (num == 1 && increment < 0)
		{
			denom++;
			increment *= -1;
		}
		else if (denom == 1 && increment > 0)
		{
			num++;
			increment *= -1;
		}
		else
		{
			num += increment;
			denom -= increment;
		}

		n--;
	}

	cout << num << "/" << denom;
	return 0;
 }

 

방법 2) 분수들을 그룹화하여 규칙성을 활용하여 구한다. 반복문을 통해 \(X\)번째 분수가 몇 번째 그룹에 속하는지와, 그룹 내에서 \(X\)가 몇 번째 분수인지를 알면 실제로 \(O(n)\)번 계산하지 않아도 \(X\)번째 분수를 바로 계산할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	
	int N = 1;		// n번째 분수가 속한 그룹 번호
	while (n > N)
	{
		n -= N;
		N++;
	}			// n이 반복문을 거치면 해당 그룹 내에서 몇 번째 분수인지를 나타내는 수로 바뀜
	
	// 짝수 번째 그룹의 분자 분모 증감 방향 = 좌하향, 분자 n으로 고정
	// 홀수 번째 그룹의 분자 분모 증감 방향 = 우상향, 분모 n으로 고정
	// N번째 그룹의 분자 + 분모 = N + 1으로 고정
	if (N % 2 == 1)
		cout << (N + 1) - n << '/' << n << endl;
	else
		cout << n << '/' << (N + 1) - n << endl;
	
	return 0;
}

 

실행 결과

아래의 결과는 방법 1)의 코드를 실행한 결과, 위의 결과는 방법 2)의 코드를 실행한 결과이다.

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.

 

---

 

조금 와전된 얘기일 수 있지만 본인의 학창 시절 기준으로 수학 I(맞나?)라는 과목에서 '여러 가지 수열' 이라는 단원을 배울 때 등장했던 '군 수열' 이라는 개념을 이용해 해결하는 문제였는데, 군 수열이라는 용어가 우리나라 고등학교 수학 외에 다른 나라에서도 실제로 쓰이는 말인지는 모르겠다. 대학교 과정에서 군 수열이라는 단어를 들어본 적은 단 한 번도 없으며, 영어로 번역하면 group(ed) sequence 또는 비스무리한 것일텐데 구글에 검색해도 딱히 뭔가 정형화된 이론이 나오지는 않는다. 사실 군 수열 문제라고 부르는 것들은 수열이 문제가 아니고 규칙성을 찾는 게 더 핵심이라 딱히 어떤 특수한 수열의 개념으로서 존재하지 않는 것 같다.