[백준] 1193 - 좌표계 도입

문제: www.acmicpc.net/problem/1193

1193번: 분수찾기

 

 

X가 주어지면 분수값을 찾아야 한다.

 

하지만 X를 가지고 바로 분수값을 찾기가 쉽지가 않다.

 

위의 표를 다음과 같은 좌표계에 대입해보자.

 

왼쪽 상단을 원점으로 하는 직교 좌표계이다.

 

그리고 분수와 분모의 합이 같은 칸끼리 선으로 이으면 위와 같이 된다.

 

저 직선의 방정식을 구해보자.

 

분수와 분모의 합이 k일 때, 계산하기 쉽게 K = k - 1 이라고 두면

 

x + y = K 이므로

 

y = - x + K 이다.

 

즉 예를 들어, 위의 그림에서 직선의 방정식은 y = -x + 5 이다.

 

y = - x + K 직선 위의 칸들 중 왼쪽 하단부터 차례로 1번, 2번, ... i번 칸이라고 하자.

 

계산의 편의를 위해 X를 다시 정의하자.

 

문제에서는 X를 지그재그로 정의했지만, 여기서 X는 왼쪽 하단부터 오른쪽 상단으로 갈수록 1씩 증가한다.

 

그 칸을 X번으로 나타냈을 때 X에 대해,

 

가 된다.

 

X에 대해 i와 K의 순서쌍이 유일하게 결정된다.

 

그리고 i와 k를 알면 분수를 쉽게 결정할 수 있다.

정확히는 위와 같다.

 

다만 위에서 X를 재정의했으므로 다시 원래대로 되돌려 놓아야 한다.

 

따라서 최종적인 결과는 아래와 같다.

 

K가 짝수일 때:

K가 홀수일 때:

 

이러한 아이디어를 이용해 코드를 작성해보면