[Python] Baekjoon 백준 1193번 분수찾기

[Python] Baekjoon 백준 1193번 분수찾기

 

문제

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

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

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

입력

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

출력

첫째 줄에 분수를 출력한다.

 

 

su = int(input())

a = 1
tmp = 0
cnt = 0
if su == 1:
    print("1/1")
else:
    for i in range(1, su):
        a = a + (i+1)
        if a >= su:
            tmp = i+1
            cnt = a - su
            break
        
    if tmp % 2 == 0:
        print("{}/{}".format(tmp - cnt, 1 + cnt))

    else:
        print("{}/{}".format(1 + cnt, tmp - cnt))

 

 

멍청해서 어떤식으로 계산할지 몰라 한참 걸렸다

풀어서 한줄로 나타내면

(진행방향 순서대로 표시함)

1/1          ---------------------------------------- 1번째

1/2  2/1          ----------------------------------- 2번째

3/1  2/2  1/3          ------------------------------ 3번째

1/4  2/3  3/2  4/1          ------------------------- 4번째

5/1  4/2  3/3  2/4  1/5          -------------------- 5번째

1/6  2/5  3/4  4/3  5/2  6/1          --------------- 6번째

7/1  6/2  5/3  4/4  3/5  2/6  1/7          ----------  ...

1/8  2/7  3/6  4/5  5/4  6/3  7/2  8/1          -----  ...

 

각 줄의 최대 숫자를 확인해서 입력받은 값이 어느 줄에 포함되는지 체크한다

1번째줄... 1

2번째줄... 3

3번째줄... 6

4번째줄... 10

...

 

예) 입력값 5 -> 3번째 줄

3번째 줄이면 분모와 분자의 최대값은 3이다

예) 입력값 13 -> 5번째 줄

5번째 줄이면 분모와 분자의 최대값은 5이다

 

이제

몇번째 줄에 해당하는지, 그 해당하는 줄의 최대숫자에서 입력받은 값을 뺀다

예) 입력값 5 , 입력값은 3번째줄에 포함 , 3번째줄의 최대값 6 , 최대값에서 입력값 빼면 1

 

그럼 그 줄의 최대값에서 바로위에 계산한값을 분모와 분자에 각각 계산해주면 되는데,

 

위에 한줄로 나타낸거 다시 보면

짝수번 째 줄 인 경우 분모가 1로 끝나고

홀수번 째 줄 인 경우 분자가 1로 끝난다

그리고

짝수번째 줄은 분자가 -1 분모가 +1 으로

홀수번째 줄은 분자가 +1 분모가 -1 으로 진행되는것을 볼수있다

 

바로위 예의 입력값이 5인 경우 해당줄의 최대값(6)에서 입력값(5) 뺀게 1이고,

해당줄은 3번째 줄로 홀수 이니까 이 줄의 최대값의 분자는 1이고, 분모는 3일 것이다

 

그럼 3번째줄의 마지막 숫자의 값는 1/3 이 되는데

여기에 아까 계산한 최대값(6)에서 입력값(5)를 뺀 결과 1을

분자에 + 1

분모에 - 1

해주면 입력값(5)에 대한 결과는 2/2 가 나온다

 

 

무식하게 했다가... 시간 초과

su = int(input())
x=1
y=1
chn = 0
tmp = [1, -1]

if su == 1:
    print("1/1")

for i in range(1, su):
    if x == 1 and y == 1:
        y += 1
        chn = 1
    else:
        if x == 1 and chn == 0:
            y += 1
            chn = 1
            tmp = [1, -1]
        elif y == 1 and chn == 0:
            x += 1
            chn = 1
            tmp = [-1, 1]
        else:
            x += tmp[0]
            y += tmp[1]
            chn = 0

print("{}/{}".format(x, y))