[백준 알고리즘] 1193번 : 분수찾기

문제

1193번 : 분수찾기

1193번: 분수찾기

 

내가 작성한 코드 (C++ 성공)

#include <iostream>

using namespace std;

int main(){
	int x;
	cin >> x;
	
	int top = 1;
	int bot = 1;
	int max = 1;
	
	bool change = true;
	
	for(int i=1; i<x; i++){
		//cout << top << "/" << bot << "   max = " << max << "\n";
		if(change == true) {
			if(bot == max) {
				bot++;
				max++;
				change = false;
			} else {
				bot++;
				top--;
			}
		} else {
			if(top == max){
				top++;
				max++;
				change = true;
			} else {
				top++;
				bot--;
			}
		}
	}
	
	if(x == 1) cout << "1/1";
	else cout << top << "/" << bot;
	
	return 0;
}

 

정리

이 문제에서 유의해야할 점은 지그재그 순서로 순서가 정해진다는 것이다.
자세히 보면 분자나 분모가 일정 숫자에 도달하면 서로의 증감이 반대가 되어 진행된다.
하지만 이러한 증감을 어떻게 짜야할 지 조금 고민이 되었다. 그래서 고민하다가 그냥 하드하게 코딩하기로 했다.

문제에 나와있는 표를 순서대로 풀어보았다.

1/1  >1/2 > 2/1 >  3/1 > 2/2 > 1/3 > 1/4 > 2/3 > 3/2 > 4/1 > ... ...

초기에 MAX의 값을 1 로 두었다. ( MAX = 1 )
처음에는 분자와 분모 둘다 1 이기 때문에 분모부터 증가가 시작된다. ( 분모 + , 분자 - )
MAX(2)에 도달했기 때문에 증가하고 있던 분모에 +1 , MAX +1 을 해주고 증감을 바꿔준다. ( 분모 - , 분자 + )
다시 분자가 MAX(3)에 도달하면 분자 +1 , MAX +1 을 해주고 증감을 바꿔준다. ( 분모 + , 분자 - )
... ... (반복) ... ...

이러한 과정을 반복하다보면 원하는 분수를 구할 수 있었다.