[파이썬] 백준 1193번 분수찾기

문제

풀이

일단 규칙성을 보자면

위와같이 라인이 하나 추가될때마다 라인 안에 들어가는 분수의 갯수는 +1 이라는 등차수열을 가지게 된다.
또한 라인이 '홀수일때는 왼쪽'에서부터 시작하며 '짝수일때는 오른쪽'부터 카운트를 한다.
5번째 라인을 예를 들면 이런 모습이다.

5는 홀수이므로 왼쪽에서 시작하며 (위 그림참조) 5개의 분수를 가지고 있다
1번째 분수 5      / 1
2번째 분수 4 (-1) / 2 (+ 1)
3번째 분수 3 (-1) / 3 (+ 1)
4번째 분수 2 (-1) / 4 (+ 1)
5분째 분수 1 (-1) / 5 (+ 1)

즉, x번째 분수를 구하기 위해서는 어느라인에 있는지 부터 확인하고 x가 포함한 n라인까지 지난 라인의 포함한 분수의 수를 뺀 후 남은수를 카운트하면 된다.

예를들어 14번째 분수를 구한다고 한다면

line 1 :			1			count =  1		x -= count	(x = 13)
line 2 :		   3 2 <-		count += 1		x -= count	(x = 11)
line 3 :	   -> 4 5 6			count += 1		x -= count	(x = 8)
line 4 :		10 9 8 7 <-		count += 1		x -= count	(x = 4)
line 5 :   -> 11 12 13 14 15	x는 4이고 line이 홀수 이므로 왼쪽에서부터 4번째 분수를 의미한다

내가 풀이한 코드

처음 내가 문제를 풀이한 방법은

x = int(input())
n = 0 # 라인의수

while x > 0: # x가 포함된 라인찾기
  n += 1     # 라인 카운트
  x -= n     # 카운트한 분수의 갯수 빼기
  
x *= -1 # 양수로 바꿔주기

if n % 2 == 0: # 라인이 짝수일때 오른쪽에서부터 카운트
  for i in range(n): #처음 분수를 짝수이기 떄문에 [n,1] 잡고 카운트 시작
    if x == 0: # x의 자리를 찾는다면
      print(f'{n - i}/{i + 1}')
      break
    else:
      x -= 1 # x의 자리까지 카운트하기
else:	# 라인이 홀수일때 왼쪽에서부터 카운트 
  for i in range(n): #처음 분수를 홀수이기 떄문에 [1,n] 잡고 카운트 시작
    if x == 0:
      print(f'{i + 1}/{n - i}')
      break
    else:
      x -= 1

처음에 내가 풀이한 방법으로도 백준에 제출을 해도 통과하는데는 무리가 없다.
하지만 다른사람의 문제풀이를 봤을때 훨씬 더 간결하게 코드를 작성한 모습을 볼 수 있었다.

while x > 0: 
  n += 1     
  x -= n 

이 코드를

while x > n:
  x -= n   
  n += 1

이런식으로 변경할 수 있다.
나는 x의 위치를 -(n - 1) ~ 0 으로 생각하여 밑에 x의 부호를 바꿔줫지만

jshane님의 코드는 x의 위치는 그냥 x가 n보다 작다면 그냥 x번째의 자리를 구하면 된다
말이 이상한데 계산하고 나온 x의 값이 3이고 라인(n)이 5라면
5번째의 라인에서 왼쪽에서부터 3번째의 분수를 구하면 되는것이다

if a % 2 == 0:
  for i in range(a):
    if x == 0:
      print(f'{a - i}/{i + 1}')
      break
    else:
      x -= 1
else:
  for i in range(a):
    if x == 0:
      print(f'{i + 1}/{a - i}')
      break
    else:
      x -= 1

이 코드 또한 x의 위치를 굳이 for문을 사용 안해도 계산을 할 수 있었다
예를 들어 전에 나의 코드는 x 가 13이라고 했을때

x    = 13 -> 12 -> 10 -> 7 -> 3 -> -2 (0부터 계산하므로 3번째에 속한다)
line = 1  -> 2  -> 3  -> 4 -> 5

x가 5번째 라인의 시작점으로 부터 3번째의 값을 계산을 했던것이다
5번째 라인이고 홀수이니 [1,5] -> [2,4] -> [3,3] 이런식으로 답을 찾았지만

  if n % 2 == 0:
      print(f'{x}/{n - x + 1}')
  else:
      print(f'{n - x + 1}/{x}')

이 식은 남은 x가 구하고자 하는 값이고

x 	 = 13 -> 12 -> 10 -> 7 -> 3
line = 1  -> 2  -> 3  -> 4 -> 5

위 결과와 같이 5번째 라인에서 3번째에 속하는 값을 구하면 되는것이다
[5, 1][4, 2][3, 3][2, 4][1, 5]

이 라인은 홀수의 라인이므로 왼쪽에서부터 시작해 3번째 값
즉, [3,3]이라는 것을 알 수 있다.

또한 x번째의 분수는

line이 짝수일때 [whlie문은 지난 x값 , line - whlie문은 지난 x값 + 1]
line이 홀수일때 [line - whlie문은 지난 x값 + 1 , whlie문은 지난 x값]

표현할수 있다

새로운 코드

x = int(input())
n = 1
while x > n:
    x -= n
    n += 1
if n % 2 == 0:
    print(f'{x}/{n - x + 1}')
else:
    print(f'{n - x + 1}/{x}')

훨씬 간결하고 보기 편한 코드가 되었다