[백준][C++] 1193 분수찾기 - 실버5

문제 보기

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

 

 

입력                          

 

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

 

 

출력                          

 

첫째 줄에 분수를 출력한다.

 

 

풀이방법                 

 

얼핏 보면 X까지 반복문을 돌려야 할 것 같겠지만,

제한시간 0.5초에 최대 10,000,000번 돌려야 할 것이기 때문에 오답일 것.

 

나는 숫자 1부터 N까지의 합을 이용해서 풀었다.

 

1/N ~ N/1 (홀수는 N/1 ~ 1/N)  분수가 놓인 대각선의 원소들의 번호는

1부터 N - 1까지의 합과 1부터 N까지의 합 사이에 놓여져있다.

 

1/1 (1)	1/2 (2)	1/3 (6)	1/4 (7)	1/5 (15)	…
2/1 (3)	2/2 (5)	2/3 (8)	2/4 (14)	…	…
3/1 (4)	3/2 (9)	3/3 (13)	…	…	…
4/1 (10)	4/2 (12)	…	…	…	…
5/1 (11)	…	…	…	…	…
…	…	…	…	…	…

 

이해를 돕기 위해 표의 분수가 몇 번째 분수인지 표시해 두었다.

 

 

예시로 8번 분수를 확인해 보자.

 

1/4 ~ 4/1 열에 놓여 있는데

1부터 3까지의 합은 6

1부터 4까지의 합은 10 이므로

6 < 8 <= 10이 성립하고 있다.

 

 

더 나아가 8 - 6 = 2이기에 해당 열의 2번째 원소라는 정보까지 얻을 수 있다.

(홀수의 경우는 1~N까지의 합에서 X를 뺀 뒤, 1을 더해주면 될 뿐임.)

 

 

전체 코드

#include <iostream>

using namespace std;

int main()
{
	int X;

	cin >> X;

	int sum = 0;
	int i = 1;
	while (true)
	{
		if (sum < X && X <= sum + i)
		{
			if (i % 2 != 0)
			{
				int denominator = (X - sum);
				int numerator = i - (X - sum) + 1;
				cout << numerator << "/" << denominator;
			}
			else
			{
				int numerator = (X - sum);
				int denominator = i - (X - sum) + 1;
				cout << numerator << "/" << denominator;
			}

			break;
		}
		
		sum += i++;
	}

	return 0;
}