백준 1193(분수찾기) 파이썬(python) 해결

문제

 

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)가 주어진다.

출력

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

 

 

---

코드

num = int(input())
start = 1
up = 2

if num == 1: #1번 분수를 찾을 경우
    print("%d/%d" %(1,1))
    exit()

while(True):
    start = start + up
    if num > start:
        up += 1
    else:
        break

num = start - num 

if up%2 == 0: #up이 짝수라면
    print("%d/%d" %(up-num, 1+num))
else: #up이 홀수라면
    print("%d/%d" %(1+num, up-num))

 

 

분수가 변경되는 규칙을 확인해 보았습니다.
지그재그로 변경되는 분수들을 규칙성에 맞게 분리해 보면 아래와 같습니다.

 

 

위의 규칙성을 분수로 나열하게 되면 아래와 같습니다.

 

 

 

규칙에 맞는 분수들의 개수는 줄이 증가할수록 1개씩 늘어납니다.
(1/2  2/1 = 2개,  3/1  2/2  1/3 = 3개, ...)

그리고 해당 규칙에서의 마지막은 짝수일 경우 분자에 위치(2/1, 4/1, 6/1)
홀수일 경우 분모에 위치(1/3, 1/5)하여 끝납니다.



다음과 같은 규칙을 활용하여 코드를 만들었습니다.

 

if num == 1:
    print("%d/%d" %(1,1))
    exit()

 

1번 분수는 규칙에서 제외시켰기 때문에 따로 출력할 수 있는 조건을 달았습니다.
출력 후에는 프로그램을 종료시키기 위해 exit() 함수를 사용했습니다.

 

 

 

 

num = int(input())
start = 1
up = 2

while(True):
    start = start + up
    if num > start:
        up += 1
    else:
        break

 

 

X번째 분수의 값을 알기 위해 X값인 num을 입력으로 받습니다.
start는 규칙에서 각 줄의 마지막 분수의 X번째 수를 의미합니다.



예로, 규칙에서 2줄의 마지막 분수는 2/1이며, 2/1은 3번째 분수이기 때문에 start = 3이 됩니다.
up은 다음 줄의 규칙을 형성하는 분수의 개수를 의미합니다.
예로, 3줄의 규칙을 형성하는 분수는 3개이며 up = 3이 됩니다.



반복 루프를 보겠습니다.
1번 분수(1/1)는 규칙에서 제외하기 때문에 바로 start(1) + up(2)을 하여
2줄의 분수들(1/2 2/1)을 다룹니다. 이때 마지막 분수는 start(3) 번째입니다.

 

입력(num)이 5라고 가정하겠습니다.
num(5) > start(3) 이 True이기 때문에 up을 1 증가시키고 다시 루프를 돕니다.
up을 1 증가시켰다는 것은 다음 줄(3줄)까지 접근하겠다는 의미입니다.
3줄의 분수들을 다룰 때 마지막 분수는 start(3+3 = 6) 번째입니다.

 

입력에서는 5번째 분수를 찾고자 하며, 3줄은 6번째 분수까지 있기 때문에 3줄에서 찾아내야 합니다.
그래서 start = 6, up = 3에서 루프가 종료됩니다.

 

 

num = start - num

if up%2 == 0: #up이 짝수라면
    print("%d/%d" %(up-num, 1+num))
else: #up이 홀수라면
    print("%d/%d" %(1+num, up-num))

 

출력을 위해 따로 변수를 만들지 않고,  num을 재사용하였습니다.
num은 start(6) - num(5)인 1의 값을 가집니다.


이것은 up(3) 줄에 있는 분수들 중 마지막 분수(6) 번째보다 1번째 이전의 분수라는 의미입니다.

 

위에서 보여준 규칙성에서 짝수 번째 줄은 분모가 1인 값으로 끝나고,
홀수 번째 줄은 분자가 1인 값으로 끝납니다.


up = 3이기 때문에 else에 들어갑니다.

출력 값에서 (1+num)은 1+1로 2가 되며, (up-num)은 2가 되어 2/2가 최종 출력입니다.
즉, 5번째 분수는 2/2라는 것입니다.

 

 

-끝-