[백준/파이썬] 1193. 분수찾기 풀이

🔗 문제 링크

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

1193번: 분수찾기

 

  처음 봤을 때는 문제가 굉장히 복잡해 보였는데 규칙을 찾고 나면 어렵지 않게 해결할 수 있는 문제인 듯하다! 이런 수학 + 구현 문제는 해결 방식을 떠올리는 게 제일 복잡한 것 같다 ㅇ0ㅇ

 

 

---

🔎 문제 풀이 & 작성 코드

  이 문제에서는 위의 화살표를 따라가며 N번째 분수를 찾아내야 한다. 내가 생각한 이 문제의 규칙성은 이렇다. 초록색 화살표로 내려가는 것과 주황색 화살표를 따라 올라오면서 이동하기 때문에, 이 특징을 가지고 알고리즘을 작성하였다.

1/1부터 시작되는 주황선은 1,3,5,...번째인 홀수 라인들이라고 생각하고, 초록선을 따라가는 줄은 2,4,6,...번째의 짝수 라인이라고 가정했다. 우선적으로 몇 번째 선 위에 찾고자 하는 분수가 위치하는지를 찾았다. 홀수 라인이라면 (m,1) → (1, m)으로, 짝수 라인이라면 (1, m) → (m,1)으로 이동하는 규칙에 따라 분수를 찾아냈다. 말로 설명하려니까 어렵다.. 

import sys
N = int(sys.stdin.readline())

loc=0
cnt=0

while N > loc:
    cnt+=1
    loc+=cnt

move = loc - N

if cnt %2 == 0 : # 짝수라인
    print(f"{cnt-move}/{1+move}")
else: # 홀수 라인
    print(f"{1+move}/{cnt-move}")

 

 

 

---

🌍 깃허브 링크

실제 작성한 해당 정답 코드는 깃허브에도 저장해두었습니다.

dohyun-99 - Overview