[C++] 백준 1193

백준의 1193번 문제 분수찾기 이다.

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

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번째 분수를 구하는 프로그램을 작성하시오.

 

 < 예제 >

슬슬 문제가 어려워지기 시작한다.

먼저 분수를 읽는 순서를 간단히 그림으로 나타내자면

이렇게 빨간색에서는 위에서 아래로, 파란색에서는 아래에서 위로 읽는다.

그러니까 순서가

1/1

1/2

2/1

3/1

2/2

1/3

1/4

2/3

3/2

4/1

이렇게 된다.

 

전체 코드를 보면 이렇다.

#include <iostream>
#include <string>
using namespace std;

int main() {

	int num;
	cin >> num;

	if (num == 1)
		cout << 1 << '/' << 1 << endl;
	else {
		int i = 1;
		while (num > i) {
			num -= i;
			i++;
		}
		if (i % 2 == 1)
			cout << i + 1 - num << '/' << num << endl;
		else
			cout << num << '/' << i + 1 - num << endl;
	}
}

먼저 입력받은 숫자가 1인 경우에는 1/1을 출력하게 하고 그 외의 경우를 정해준다.

 

		int i = 1;
		while (num > i) {
			num -= i;
			i++;
		}

while문을 통해 숫자가 몇번째 대각선에 위치해 있는지 확인한다.

num에 10이라는 값이 나온다면 while문은 조건식이 참일경우에 계속 반복하므로 

1) num -= i -> num = 10-1 = 9  / i++ -> i = 2    == 9 > 2

2) num -= i -> num = 9 - 2 = 7  / i++ -> i = 3    == 7 > 3

3) num -= i -> num = 7 - 3 = 4  / i++ -> i = 4    == 4 > 4

여기서 num > i의 조건에 만족하지 않기 때문에 num(10)은 i = 4, 4번째 대각선에 포함되는 것이다.

 

		if (i % 2 == 1)
			cout << i + 1 - num << '/' << num << endl;
		else
			cout << num << '/' << i + 1 - num << endl;

 

그리고 얻은 i값을 통해 위치에 어떤 분수가 들어갔는지 확인해주면 된다.