[BOJ / 파이썬] 1193 : 분수찾기

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

1193번: 분수찾기

 

Sol )

1. 입력받은 n이 몇 번째 대각선에 포함되는지 찾은 후 대각선의 가로 혹은 세로 시작점 (a/1 또는 1/a 형태)의 순서와 n 번째 순서까지의 차이를 계산해서 정답 출력
2. 대각선 : 첫번째 선 ( 1/1 ), 두번째 선 (1/2, 2/1), 세번째 선 (3/1, 2/2, 1/3) 
3. 첫 번째 선에서 두 번째 선으로 이동할 때 가로 순서 증가량은 1, 세로 증가량은 2 이다.
4. 두 번째 선에서 세 번째 선으로 이동할 때 가로 순서 증가량은 4, 세로 증가량은 1 이다.
5. 홀수번째 선(= x)에서 짝수번째 선으로 이동할 때 가로는 항상 1 증가, 세로는 2 + 4 * (x/2)의 몫 씩 증가
6. 짝수번째 선(= x)에서 홀수번째 선으로 이동할 때 세로는 항상 1 증가, 가로는 4 * (x/2)의 몫 씩 증가

소스코드 )

 

n = int(input())
cnt = 1
diff = 4
r,c = 1,1
row_diff = 2
col_diff = 4
up = down = 1

while r<n and c<n and n!=1:
  if cnt%2 != 0:
    r += row_diff
    c += 1
    row_diff += 4
  else:
    r += 1
    c += col_diff
    col_diff += 4
  cnt += 1

if r>c:
  up = 1
  down = cnt
  while c != n:
    down -= 1
    up += 1
    c += 1
  
elif c>r:
  up = cnt
  down = 1
  while r != n:
    down += 1
    up -= 1
    r += 1

print(f"{up}/{down}")