백준 파이썬 코딩테스트 (분수찾기)

---

백준 1193번 문제

분수찾기

---

문제

 

---

풀이

1.

우선은 이 문제를 위해서 규칙성을 찾아보았다.

이미지로 되어있어서 규칙의 파악은 쉬웠다.

자 홀수번대는 분자가 메인, 짝수번대는 분모가 메인이다.

 

이 말인 즉슨 메인이 최대 값이라는 의미이다.

1/1은 패스를 하고 3을보자. 3은 홀수니까 3/1로 스타트를 한다.
이때 3/1 다음은 각 분자 -1, 분모 +1을 한 2/2 그리고는 1/3이다. 
다음은 4 즉 짝수니 1/4로 되는 것이다.

 

그리고 이를 통해서 최대 반복값도 알 수 있다. 1/4는 최대 4번 1/4 > 2/3  > 3/2 > 4/1 이 최대 갯수이다.

 

자 이를 이용해보자.

우선 area매개변수에 while을 사용해서 area가 인풋보다 커지면 스톱시킨다.

area에는 반복마다 area+1을 더한다. 즉 2번 반복하면 1+2로 3이 될 것이다.

 

이때 인풋이 12로 가정해보자. 이는 5번의 반복 즉 area가 15가 되면 멈출 것이다.

 

이 5번의 반복과 15를 이용해서 문제를 풀 것이다.

 

5번의 반복은 즉 홀수 5/1 스타트로 볼 수 있다. 5/1은 11번째 일것이다. (4반복시 최대값이 10이라)

즉  area의 숫자 마지막이 최대값 이된다. 4번반복은 1+2+3+4 는 10 이며 4/1은 10번째 숫자. 이런식으로.

 

그러면 최대값으로 해서 15는 1/5일 것이다. 여기서 인풋이 12 니까, 15를 빼게되면 3.

최대값에서 각 +3, -3을 하게되면 된다. 그러면 12번째의 숫자는 4/2가 될 것이다.

 

 

 

>> 

원래는 area += area + 1 을 했는데 생각해보니, 이러면 1, 3, 7 ... 으로 기하급수적으로 숫자가 커지는 거였다.

1+2+3... 을 하기 위해서 count를 사용했다. 결국 라인을 알기위해서는 필요했다.

---

결과

import sys
X = int(sys.stdin.readline())
area = 0
count = 0

while area < X:
    count += 1
    area += count
    
n = count - (area - X)
m = 1 + (area - X)

if count%2 == 0:
    print(f"{n}/{m}")
else :
    print(f"{m}/{n}")

 

 

Coding_Test/백준/Silver/1193. 분수찾기 at main · K-MarkLee/Coding_Test · GitHub

Coding_Test/백준/Silver/1193. 분수찾기 at main · K-MarkLee/Coding_Test