백준 1193 : 분수찾기

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

내 풀이

간단한 구현 문제이다.

 

입력값인 X가 10,000,000이므로 $O(n)$ 정도로 끝내야 한다.

 

X번째 수를 알기 위해서는 위치에 대한 정보가 필요하다.

1. 몇번째 대각선에 X번째 수가 위치하는지, 2. 몇번째 대각선에서 (위나 아래로부터) 또 몇번째 위치에 있는지

를 알아야 한다.

 

1. 몇번째 대각선에 X번째 수가 위치하는지는
X에서 첫번째 대각선의 원소 개수를 빼고
X에서 두번째 대각선의 원소 개수를 빼고
X에서 세번째 대각선의 원소 개수를 빼다가...

X가 0보다 작아지는 그 대각선의 위치를 구하면 된다.

 

그런데 나는 이 "대각선의 원소 개수"가 공차가 1인 등차수열이길래

"총 대각선의 원소 개수"를 구하기 위해

$\frac{n(n+1)}{2}$식을 이용하고자 했다.

 

2. 몇번째 대각선에서 (위나 아래로부터) 또 몇번째 위치에 있는지를 구해야

적합한 분모, 분자를 구할 수 있다.

 

그런데 또 2번을 구하려면, 이 대각선이 홀수번째인지 짝수번째인지를 알아야 한다.

왜냐하면, 그에 따라 순서를 세는 방향이 변하니까.

이것은 단순히 구해놓았던 1번을 가지고 나머지를 구해보면 된다.

 

2번 같은 경우는 바로 앞에서 구한 "홀짝"에 따라 1번에서 구한 "총 대각선의 원소 개수"를 X에서 빼주면 나온다.

 

이렇게 구한 위치 값들을 바탕으로 작성한 코드는 아래와 같다.

x = int(input())
n = 1
while True:
  if n * (n+1) / 2 >= x:
    break
  n+=1

if (n+1)%2 == 0:
  order = x - ((n-1)*n // 2)
  denominator = order
  numerator = n + 1 - denominator
  print(str(numerator) + "/" + str(denominator))

else:
  order = x - ((n-1)*n // 2)
  numerator = order
  denominator = n + 1 - numerator
  print(str(numerator) + "/" + str(denominator))

 

참고풀이

그런데 굳이 이렇게 복잡하게 풀 필요는 없었다.

몇번째 대각선인가를 구할 땐, 굳이 등차수열 식을 활용하지 않아도,

그냥 1, 2, 3, 4, 5, 6..을 X에서 빼는 방식으로도 구현할 수 있다.

 

또한 X에서 다시 "총 대각선의 원소"를 빼보지 않아도, 위에서 "몇번째 대각선"인지를 구할 때

미리 빼어두면 된다.

 

print문에서 f를 통해 서식을 할 수 있다는 점도 배웠다.

변수 초기화 시 한 줄에 몰아서 가능하다는 점도 배웠다.

 

따라서 수정된 코드는 아래와 같다.

x = int(input())

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

top, bottom = 0, 0
if diagonalOrder % 2 == 0:
  top = x
  bottom = diagonalOrder + 1 - x
else:
  top = diagonalOrder + 1 - x
  bottom = x

print(f"{top}/{bottom}")