백준 온라인 저지 - 분수찾기(#1193) 파이썬

문제설명

2차원 배열에 분수가 담겨있고, 이는 아래로 향하는 (X, Y) 좌표로도 볼 수 있습니다. 이 배열의 형태도 마찬가지로 문제 해결을 위해서는 규칙성을 찾아야 합니댜. 저는 배열의 대각선을 또다른 배열로 보았습니다. 단, 지그재그 순서로 분수에 번호를 매기기 때문에 첫번째 배열은 1/1, 두번째 배열은 2/1, 1/2, 세번째 배열은 3/1, 2/2, 1/3이 담겨있고, N번째 배열에는 N개의 배열이, N이 홀수라면 N/1, N-1/2 .. 1/N 순서로, 짝수라면 역순으로 담겨있겠죠? 또한 지그재그 형태로 지나가면서 분수에 번호를 매기기 때문에 각 배열에 포함된 분수의 갯수의 합으로 이루어진 수열, 1, 1+2, 1+2+3.. 순으로 증가하는 수열, 등차수열이 포함된 계차수열입니다. (계차수열에 관한 자세한 설명은 벌집(#2292) 게시물에서 확인하실 수 있습니다.) 

 

우선 k는 k번째 대각선 배열, a는 k번째 배열의 가장 큰 번호입니다. 일반항을 구해보면 a = ((k**2) + k)/2가 나오고, 벌집문제와 마찬가지로 while문에 k가 1부터 1씩 증가하는 형태로 x가 a보다 작거나 같아질 때 x가 짝수와 홀수인 경우를 나누어 짝수라면 k-(a-x)/ a-x+1이, 홀수라면 a-x+1/k-(a-x)가 출력될 수 있도록 if문을 이용해 코드를 구성했습니다. 

 

분수찾기 #1193 파이썬 코드

x = int(input())
k = 1
while True: 
  a = ((k**2) + k)/2  # a는 각 대각선 배열의 끝에 위치한 분수의 번호를 담은 계차수열 일반항, k는 배열의 번호
  if x <= a:
    if k % 2 == 1:
      print("%d/%d"%(a-x+1, k-(a-x)))
    else:
      print("%d/%d"%(k-(a-x), a-x+1))
    break
  k += 1