[백준 문제 C++] 1193 분수찾기

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

1193번: 분수찾기

배열 인덱스에 해당하는 곳을 지그재그로 출력하는 문제이다.

 

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

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

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

...    ...    ...   ...   ...

 

[1]      [2]       [3]      [4]      [5]      [6]      [7]

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

식으로 진행이 된다.

 

규칙을 먼저 찾아보면

1. 최대 숫자가 1, 2, 3, 4 순서대로 증가한다.

ex)
 1 시작 => 1/1

 2 시작 => 1/2, 2/1

 3 시작 => 3/1, 2/2, 1/3

 

2. Ascending (오름차순 ex: 1 2 3 4) , Descending (내림차순 ex: 4 3 2 1)이 반복되는 형태로 되어있다.

 

2번 규칙 순서가 바뀌는 것을 제외하고 1번 규칙만을 놓고 나열을 해보면 아래와 같이 숫자가 나열 된다.

1/1

1/2 2/1

1/3 2/2 3/1

1/4 2/3 3/2 4/1

 

잘 보면

X / 최대 숫자

X + 1 / 최대 숫자 - 1

...

이런식으로 흘러가는 걸 알 수 있다.

이걸 이용해서

 

X - 최대 숫자 > 0 이면

   X = X - 최대숫자, 최대숫자 증가

X - 최대 숫자 <= 0 이면

   오름차순 or 내림차순 순서에 따라 X / 최대 숫자 - X + 1 또는 최대 숫자 - X + 1 / X

  를 출력해주기만 하면 된다. (이렇게 작성함)

 

#include <iostream>

using namespace std;

int main()
{
	int x;
	int num = 1;
	bool isAscending = true;

	cin >> x;

	while (true)
	{
		isAscending = !isAscending;

		if (x - num <= 0)
		{
			if (isAscending)
			{
				cout << x << "/" << num - x + 1 << endl;
			}
			else
			{
				cout << num - x + 1 << "/" << x << endl;
			}

			break;
		}

		x -= num;
		num++;
	}
}