[기초수학] 1193. 분수찾기 - C++

| 1193. 분수찾기

Category :

기초 수학

Title :

1193. 분수찾기

Rank :

Bronze

Language :

C++

Question :

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

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

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

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

Limited - Time :

0.5 Sec

Limited - Space :

256 MB

Code :

#include<iostream>
class cl_solution{
public :
	void fn_run(int user_data);
};
void cl_solution::fn_run(int user_data){
	int diagonal=0,sum=0, key=0;
	while (sum < user_data) {
		diagonal++;
		sum+= diagonal;
	}
	key = sum - user_data;
	if (diagonal % 2==1 )
		std::cout << key + 1 << '/'<< diagonal - key << "\n";
	else
		std::cout << diagonal - key << '/' << key + 1 << "\n";
}
int main() {
	int user_data=0;
	cl_solution sol;
	std::cin >> user_data;
	sol.fn_run(user_data);
	return 0;
}

Solution :

이러한 문제는 규칙성을 찾아내는 것이 가장 중요한데 위 문제는 아래와 같은 것을 볼 수 있다.

지그 재그 형태로 규칙성을 가지고 있다.

어렵다면 분자를 기준으로 보면 조금 더 명확하게 이해가 간다.

이때 대각선의 합을 보면 MAX 숫자를 도출 할 수 있다. 

1, 3, 6, 10, 15...

그럼 여기서 구현해야 하는 부분을 간략적으로 알 수 있다.

1. 몇 번째 대각선에 속하는가?

2. MAX 값 안에 속하는가?

while (sum < user_data) {
	diagonal++;
	sum+= diagonal;
}

MAX 값과 User_data를 통하여 몇 번째인지 유추 할 수 있는 키값을 구할 수 있다.

key = sum - user_data;

 

대각선의 패턴을 보게 되면 

홀수번째 패턴은 i/1, (i-1)/2, (i-2)/3, ..., 1/i 을 볼 수 있으며

짝수번째 패턴은 1/i, 2/(i-1), 3/(i-2), ..., i/1 을 볼 수 있다.

	if (diagonal % 2==1 )
		std::cout << key + 1 << '/'<< diagonal - key << "\n";
	else
		std::cout << diagonal - key << '/' << key + 1 << "\n";

결과 :

BackJoon :

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

1193번: 분수찾기

GitHub :

https://github.com/Anchangun/BaekJoon/tree/main/Question/Math/Calculation/1193.%20%EB%B6%84%EC%88%98%EC%B0%BE%EA%B8%B0

GitHub - Anchangun/BaekJoon