[백준 알고리즘/python] 백준 1193번 분수찾기, 파이썬

백준 알고리즘 1193번 분수찾기, 파이썬

 

이번에 풀어 볼 문제는 백준 알고리즘의 1193번 분수찾기 문제이다.

파이썬으로 풀어보았다.

 

나는 머리가 딸려서 그런가 문제 이해하는데 한참 걸린거 같은데, 한번 표에 화살표를 그려봤다.

수열이 저런식으로 진행이 되는데 저기서 X가 주어지면 X번째에 있는 분수를 구하는 프로그램이다

 

일단 문제에 대한 생각이다.

#생각 1. 지그재그가 시작되는 첫 원소?를 잘 살펴보면 첫째줄 (1/1) 둘째줄 (1/2) 셋째줄(3/1) 

            분자나 분모가 그 줄이 몇번째인지를 알려주고 있다.

#생각 2. 그 줄이 몇번째인지 알면 당연히 그 줄에 있는 원소의 개수도 알 수 있다. 1>1 2>2 3>3

#생각 3. 1과 2를 가지고, X를 입력받았을때, X보다 처음으로 크게 나오는 1 + 2 + 3 ... +N을 구하면

            N이 바로 X를 가지고있는 줄이다.

#생각 4. 이제 N에서 X가 몇 번째인지 알아야하는데 그건 간단하다, X에서 1부터 N-1까지의 합을 빼면된다.

#생각 5. 몇 번째인지 알았으면 분모나 분자가 1씩 작아지고 커지는 규칙을 이용해서 답을 출력한다.

 

위와 같이 생각하고 짜 내려간 코드이다.

num = int(input())
count = 1

while True:
    if num > int(count*(count+1)/2):
        count = count + 1
    else:
        break

result = num - (count-1)*(count)/2

str1 = str(int(result))
str2 = str(int((count-(result-1))))
if count % 2 == 0:
    print(str1 +'/'+str2)
else:
    print(str2+'/'+str1)

이렇게 제출하니 정답으로 인정이 되었다.

str을 쓴 이유는 str을 쓰지 않으면 분수가 계산이 되어서 소수값으로 나오기 때문이다.

간단했는데, 문제 이해하는데 시간이 좀 걸렸다

 

문제 출처

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

1193번: 분수찾기