BOJ 1193 - 분수찾기

문제 링크

문제#

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

이와 같이 나열된 분수들을 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개, 2번째 대각선에는 2개, 3번째 대각선에는 3개가 있으므로, 먼저 X가 몇 번째 대각선에 있는지 찾으면 된다.

코드에서는 1 + 2 + ... + i 형태로 누적 개수를 늘려 가며 X가 포함되는 대각선을 찾는다. 그다음 그 대각선 안에서 X가 끝에서 얼마나 떨어져 있는지를 num = n - X로 계산해 분자와 분모를 정한다.

대각선 번호가 홀수인지 짝수인지에 따라 진행 방향이 반대라는 점이 핵심이다. 홀수 대각선이면 분자가 증가하고, 짝수 대각선이면 분모가 증가하는 형태로 값을 만들면 된다.

코드#

#include <iostream>
#include <string>
using namespace std;
 
int X, n = 1, i = 1;
string ans;
 
void solve() {
	while (true) {
		if(X <= n) 
			break;
		i++;
		n = n + i;
	}
 
	int num = n - X;
 
	if(i % 2) //홀수
		ans = to_string(1 + num) + "/" + to_string(i - num);
	else //짝수
		ans = to_string(i - num) + "/" + to_string(1 + num);
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	cin >> X;
 
	solve();
 
	cout << ans << '\n';
 
    return 0;
}

복잡도#

• 시간 복잡도: 목표 위치가 포함된 대각선을 찾을 때까지 증가시키므로 $O(\sqrt{X})$이다.
• 공간 복잡도: 몇 개의 변수만 사용하므로 $O(1)$이다.

마무리#

배열 전체를 직접 따라갈 필요 없이, 대각선 번호와 그 안에서의 위치만 찾으면 답이 바로 나온다. 지그재그 규칙을 수열처럼 바꿔 보는 것이 포인트다.