[백준] 단계별 문제풀이 #1193 - 분수찾기

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1 1/2 1/3 1/4 1/5 …
2/1 2/2 2/3 2/4 … …
3/1 3/2 3/3 … … …
4/1 4/2 … … … …
5/1 … … … … …
… … … … … …
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

풀이

아이디어

1. 대각선 라인수와 칸이 동일하다.
   (ex. 1 번째 라인, 칸 1개. 2 번째 라인, 칸 2개)
2. 지그재그 순서로 진행하며, 라인의 끝 점까지의 칸 수를 End 로 둔다.
   (End = {1, 3, 6, 10, 15, ... } )
3. 내가 찾고자 하는 번째 수는 이미 지나친 끝점을 제외하고, 찾고자 하는 라인에서 몇칸 갈지만 알면 찾을 수 있다.
4. 각 라인의 분수는 분자와 분모값의 합이 동일하며, 합은 (라인수 + 1) 이다. 따라서 [분자값 + 분모값 = 라인수 + 1]
   (ex. 3번째 라인 [분자값 + 분모값 = 4] , [라인수 + 1 = 4])
   즉, 분자와 분모값은 합을 나눠가진다. 분자가 커지는 만큼 합에서 가져가고, 분모는 합에서 남은 걸 가진다.
5. 라인수가 홀수인 경우,
   분모값은 1부터 1씩 커지므로, 해당 라인에서 진행할 칸수가 분모값이 된다.
   분자값은 합에서 분모값 뺀 값, (라인수 + 1) - 분모값 이다.
   라인수가 짝수인 경우는 분모,분자 값을 반대로 가져오면 구할 수 있다.

코드

x = int(input())

#라인수와 끝점 구하기
line = 0
end = 0
while x:
    line += 1
    end += line
    if x - end <=0:
        end -= line
        break

#끝점 제외 후 진행할 수 구하기
diff = x - end

#홀수인 경우 분모에 진행할 수, 분자에 합에서 분모 제외한 수 저장하기
#짝수인 경우는 분자, 분모를 반대 방법으로 저장
if line % 2:
    denomi = diff
    numer = line + 1 - denomi
else:
    numer = diff
    denomi = line + 1 - numer

print("{}/{}".format(numer,denomi))

검토

처음 규칙과 해법을 찾지 못해 한참을 헤맸다.
홀,짝 라인의 규칙을 찾지 못한 것이 큰 패착이다...

분자와 분모값을 각각 나열해 봤을 때, 특정 주기가 있다는 것을 안 나머지...
그 주기들을 나열한 수열이 등차수열이라 등차수열 합으로 끝점을 잡아 찾았다.
끝점 이후 얼만큼 진행할지는 주기에 해당하는 수열의 중간 값에서 떨어진 만큼을 통해 구했다.

아주 복잡하고도 비효율적인 방법으로 풀었지만 뿌듯했다 ^^

뻘짓을 기념하며 저세상 코드는 박제해 둔다.

x = int(input())
import math

if x == 1:
    numerator = 1
    denominator = 1
elif x == 2:
    numerator = 1
    denominator = 2
elif x == 3:
    numerator = 2
    denominator = 1
else:
    #분자 건너뛸 수
    for i in range(x):
        if x - (2 * (i ** 2) - i) < 0:
            break
    numerMaxIdx = i - 1

    #분자 진행할 수
    numerCnt = x - (2 * (numerMaxIdx ** 2) - numerMaxIdx)
    if numerCnt == 0:
        numerCnt = 1
    #분자 반복 주기 수
    numerFrequency = 1 + (4 * numerMaxIdx)
    #분자 중간 값
    numerMiddle = math.ceil(numerFrequency / 2)
    #분자
    numerator = numerMiddle - abs(numerMiddle - numerCnt)

    #분모 건너뛸 수
    for i in range(x):
        if x - (2 * (i ** 2) + i) < 0:
            break
    denomiMaxIdx = i - 1

    #분모 진행할 수
    denomiCnt = x - (2 * (denomiMaxIdx ** 2) + denomiMaxIdx)
    if denomiCnt == 0:
        denomiCnt = 1
    #분모 반복 주기 수
    denomiFrequency = 3 + (4 * denomiMaxIdx)
    #분모 중간 값
    denomiMiddle = math.ceil(denomiFrequency / 2)
    #분모
    denominator = denomiMiddle - abs(denomiMiddle - denomiCnt)

print("{}/{}".format(numerator,denominator))

출처 : https://www.acmicpc.net