[백준] #21193 분수 찾기 python

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

1193번: 분수찾기

 

여러 반복 패턴을 파악하자.

 

N이 1일 때는 1/1로 예외를 처리하고, 규칙성을 발견한다.

 

N이 2, 3은 각각 1/2, 2/1 으로 구성,

 

N이 4, 5, 6은 각각 3/1, 2/2, 1/3 으로 구성,

 

 

N이 7, 8, 9, 10은 각각 1/4, 2/3, 3/2, 4/1 으로 구성되어 있다.

 

그래서, 규칙성을 살피면 N의 개수에 따라 규칙성이 있다.

 

이를 테면, 2개의 숫자에 대해 1/2, 2/1의 합은 1+2, 2+1 = 3으로 되어 있다. 이 경우, size는 3이고 count는 2이다.

 

그리고 그 다음은, count 3에 대해 size 4를 갖는다.

 

규칙성이 보이시죠 ?

 

한편, count가 짝수일 때는 분수가 1보다 작은 것부터 시작, count가 홀수일 때는 1보다 큰 것부터 시작한다는 것에 주목하여 문제를 풀이하여 주시기 바랍니다.

 

제가 제출한 코드는 아래와 같습니다.

 

 

N = int(input())

cnt = 1
result = 1
while True:
    if N == 1:
        print("1/1")
        break
    elif N <= result:
        size = cnt + 1
        if cnt % 2 == 0:
            start, end = result - cnt + 1, result
            tmp_N = N - start
            val_list = []
            for i in range(1, size):
                val_list.append((i,size-i))
            print(str(val_list[tmp_N][0])+"/"+str(val_list[tmp_N][1]))
            break
        elif cnt % 2 == 1:
            start, end = result - cnt + 1, result
            tmp_N = N - start
            val_list = []
            for i in range(size-1, 0, -1):
                val_list.append((i,size-i))
            print(str(val_list[tmp_N][0])+"/"+str(val_list[tmp_N][1]))
            break
    cnt += 1
    result += cnt