BOJ 1193번 : 분수찾기

안녕하세요. 지난 포스팅의  BOJ 2292번 : 벌집에서는 계차수열을 활용해서 문제를 풀어보았습니다. 오늘도 역시 수열과 관련된 문제를 풀어보도록 하겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 그룹 수열(Group Sequence)

 

제출 코드

X = int(input())

G = 1
while (G * (G - 1)) // 2 < X : 
    G += 1
G = G - 1
N = X - (G * (G - 1)) // 2
if G % 2 == 0 : print(str(N) + '/' + str(G - N + 1))
else : print(str(G - N + 1) + '/' + str(N))

 

해설

사실 이 문제는 그룹 수열 자체를 이해하는 것이 중요한게 아니라 얼마나 규칙성을 잘 찾는 지가 중요합니다. 일단, 문제를 분석해보면 어떤 $X$가 주어졌을 때 규칙에 맞게 분수를 배열했을 때 $X$번째 분수를 찾는 것이 목표입니다. 각 분수를 배열해보면 아래와 같습니다. 

 

$$\frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{3}{1}, \frac{2}{2}, \frac{1}{3}, \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1}, \dots $$

 

이렇게 보면 딱히 규칙성이 없어보이네요. 따라서 아래와 같이 격자를 표시해보겠습니다. 

 

$$\frac{1}{1} | \frac{1}{2}, \frac{2}{1} | \frac{3}{1}, \frac{2}{2}, \frac{1}{3} | \frac{1}{4}, \frac{2}{3}, \frac{3}{2}, \frac{4}{1} | \dots $$

 

이제 저희는 각 격자별로 1번 그룹, 2번 그룹, 3번 그룹, 4번 그룹, ... $G$번 그룹이라고 하겠습니다. 따라서 목표는 $X$번째 분수가 $G$번째 분수 그룹의 몇 번째 분수인지 확인하는 것으로 바뀝니다. 따라서 두 가지 단계로 이 문제를 풀 수 있을 거 같습니다. 

 

STEP1. 해당 분수가 몇 번째 그룹($G$)에 속하는 지 찾기

일단, $X$가 주어졌다고 가정하겠습니다. 그렇다면 $X$번째 분수가 몇 번째 그룹에 속하는 지 확인하기 위해서는 어떻게 해야할까요? 방법은 간단합니다. $X$의 의미가 무엇인지를 다시 생각해보도록 하죠. $X$란 $X$번째 분수가 속한 그룹보다 작은 모든 그룹들이 속한 분수들의 개수의 합보다는 작아야합니다. 이때, $G$번째 그룹은 $G$개의 분수가 속한다는 것을 인지하신다면 아래와 같은 부등식을 얻을 수 있습니다. 

 

$$1 + 2 + \cdots + (G - 1) = \frac{G(G - 1)}{2} < X$$

 

위 부등식을 만족하는 $G$는 여러 개가 있을 수 있습니다. 그 중에서 가장 큰 $G$가 $X$번째 분수가 속한 그룹의 바로 이전 그룹이 될 것입니다. 이를 저는 위 코드에서 while 문을 이용해서 구현하였습니다. 그 다음에 $G$에서 1을 빼게 되는 데 이는 $\frac{G(G - 1)}{2} < X$를 만족하지 않으면 종료됩니다. 그 순간 $G$에 1이 더해지기 때문에 저희가 원하는 값이 나오지 않아 1을 빼주는 것 입니다. 

 

STEP2. 해당 그룹($G$)에서 몇 번째 분수($N$)인지 찾기

$X$번째 분수가 어떤 그룹에 속하는 지 알았다면 해당 그룹에서 몇 번째 분수인지 알아봐야합니다. 이는 아주 간단합니다. 다만, $G$가 짝수인지 홀수인지에 따라서 나뉘게 됩니다. 

 

- $G$가 짝수인 경우 : $\frac{1}{G}, \frac{2}{G - 1}, \frac{3}{G - 2}, \dots, \frac{N}{G - N + 1}, \dots, \frac{G}{1}$

- $G$가 홀수인 경우 : $\frac{G}{1}, \frac{G - 1}{2}, \frac{G - 2}{3}, \dots, \frac{G - N + 1}{G}, \dots, \frac{1}{G}$

 

그러므로 저희는 $G$가 짝수일 때는 $\frac{N}{G - N + 1}$을 출력하면 되고 $G$가 홀수일 때는 $\frac{G - N + 1}{G}$를 출력하면 됩니다. 그렇다면 $N$을 알아야겠네요. 이 역시 간단하죠. $\frac{G(G - 1)}{2}$이 $X$가 속한 그룹($G$)보다 작은 모든 그룹의 분수들의 개수의 전체 합이라면 $X - \frac{G(G - 1)}{2}$는 남은 분수의 개수이므로 이 값이 $N$이 됩니다. 

 

참고자료 및 그림출처

백준 코딩 문제