분수찾기 풀이

문제 링크: https://www.acmicpc.net/problem/1193

백준 기본 수학 1 3단계 - 1193번 분수찾기를 풀어보았다.

 

풀이: 분자 혹은 분모의 최댓값과 한 대각선에 있는 분수 번수의 최댓값을 알아야 한다. 예를 들어, 8번째 분수인 2/3은 1/4->2/3->3/2->4/1 대각선에 위치해 있고, 이 대각선에서의 분자 혹은 분모의 최댓값은 4이고, 분수 번수의 최댓값은 10이다. 그래서 구하고자 하는 x번째 분수가 어느 대각선에 위치해 있는지를 알아내고, 그 대각선이 어느 순서대로 번수가 증가하는지를 파악해 x를 알아내면 된다.

 

C++

#include <iostream>

using namespace std;
int main()
{
  int x;  // 입력
  cin>>x;
  int count=0;  // 지그재그의 순서
  while(x>0)  // x = 떨어져 있는 거리
  {
    count++;
    x-=count;
  }
  if(count%2==0) cout << count+x << "/" << 1-x; // 짝수면 분자가 증가
  else cout << 1-x << "/" << count +x; // 홀수면 분모가 증가
}

Python

x=int(input())
sum=0 # 한 대각선에 있게 되는 분수의 최대 번수
cnt=0 # 분모 혹은 분자의 최댓값
while x>sum:
	cnt+=1
	sum+=cnt
if cnt%2==0: # 짝수면 아래->위 방향으로 번수가 증가
	up=cnt
	down=1
	for i in range(sum-x):
		up-=1
		down+=1
else: # 홀수면 위->아래로 번수가 증가
	up=1
	down=cnt
	for i in range(sum-x):
		up+=1
		down-=1
print(f'{up}/{down}')

Java