[python]1193.분수찾기

 내분수가 어느정도인지 알게해준 문제다. 자괴감든다.

어쨋든 코드 설명전 아이디어를 말하겠다.

 

대각선으로 분수를 지그재그로 나열했을 때 몇번째 분수를 찾을것인지 입력값으로 주어지면 해당 번째에 있는 분수를 출력해주는 문제이다.

 

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

짝수번째 대각선라인의 분수들은 분모는 -1씩 작아지고, 분자는 +1로 숫자가 바뀌고, 홀수번째 대각선라인의 분수들의 분모는 +1,분자는 -1로 작아진다. 그리고 각 분모 분자의 숫자는 몇번째 라인인지에 따라 숫자 범위가 달라진다. 예를 들어 3번째라인의 분수는 3/1, 2/2, 1/3인데 3번째라인은 홀수라인기때문에 분모가 +1로 증가하고, 분자가 -1씩 작아지는 규칙이 있다.

 

 그러면 입력값이 몇 번째라인의 몇 번째 숫자인지는 어떻게 알까?

첫번째 대각선 라인의 분수는 1개 위치해있고, 두번째 대각선 라인의 분수는 2개가 위치해있다. 결구 n번째라인에 n개의 분수가 있다는 것. 이것을 통해 몇번째 라인인지 알 수 있다. 입력값 x가 첫번째라인에 존재한다면 1이어야 하고, 두번째라인에 존재한다면 2또는 3이어야하고, 세번째 라인에 존재한다면 4, 5 또는 6일 것이다.

예를들어, 만약 주어진 수가 8일때 1+2+3+4=10이기때문에 4번째라인의 분수라는것을 알 수 있다. 4번째 라인임은 1+2+3+4=10이고 8이 10보다 작기때문에 4번째 줄인 것을 알아내었다.(즉 10은 4번째줄의 가장 마지막 분수임을 알 수 있다.)

그러면 8은 4번째라인의 몇 번째 분수일까?

10이 마지막 즉 4번째 라인의 4번째 분수이다. 그러면 4번째 라인의 첫번째 분수는 지그재그 순서로 나열된 분수들 중에서 몇번째인지 알 수 있다. 4번째라인에는 아까도 말했다시피 4개의 분수가 존재하기 때문에 4번째 라인의 첫번째 분수는 지그재그 순서에서는 7번째 분수임을 알 수 있다. 즉 입력값x가 7일 때가 4번째라인의 첫번째 분수라는 것!

이것을 알고 코드를 짜면

 

x = int(input())
addn=0 #line
s=0
up=1
down=1
 
while True:
    s+=addn
    if x==s or x<s:
        break
    addn+=1
first=s-addn+1 #해당라인의 첫번째 
i=x-first+1
 
if addn % 2 == 0:  # 짝수번째 라인일 경우 => 분모는 오름차순, 분자는 내림차순
    up = i
    down = (addn + 1) - i
    result=("{}/{}".format(up, down))
else:  # 홀수번째 라인일 경우 =>분모는 내림차순,분자는 오름차순
    up = (addn + 1) - i
    down = i
    result=("{}/{}".format(up, down))
 
print(result)

 

www.acmicpc.net/problem/1193