백준 분수찾기 1193번 - 시간제한이 있을 때

sys.stdin.readline()

백준 1193번은 시간제한 0.5초가 있다. 보통 이럴 때는 Input보다는 sys을 이용해서

위와 같이 입력을 받아주는게 좋은 것 같다.

그리고 for문 중복이나 반복문 중복을 피하기가 어려울 때, 불필요한 연산을 하지 않도록 만들어주어야 한다. 어찌보면 당연하지만, 1193과 같은 문제를 보면

백준 1193번 문제 사진

n 번째 분수를 찾아야하는데 그 전 번째 분수까지 계산하는 과정을 최소로 줄여야 시간제한을 벗어날 수 있다. 

처음에는 차근차근 문제를 푼다고 n번째 분수를 찾느라 그 전 번째 분수 계산과정까지 반복문에 넣다보니 시간 초과가 났다.

규칙을 잘 파악해서 딱 n번째 분수를 찾을 수 있도록 구상을 해야했다.

import sys

n = int(sys.stdin.readline())
arr = []
Sum = 0
limit = 0
for i in range(1,n+1):
    Sum += i
    if Sum >= n:
        limit = i
        break



if (limit%2 == 1):
    k = limit
    for i in range(1,limit+1):
        arr.append(str(k)+'/'+str(i))
        k -= 1
else:
    k = limit
    for i in range(1,limit+1):
        arr.append(str(i)+'/'+str(k))
        k -= 1
print(arr[n-Sum-1])

나는 위와 같은 코드를 작성했는데, limit을 정해서 필요한 분수찾기에 제한을 뒀고

문제 풀이 구상 과정

위와 같이 묶어서 n번째가 과연 해당하는 3(홀수에서는 분자가)또는 4(짝수에서는 분모가)등,, 이로 시작하는 분수 배열에서 몇 번째인지 어떻게 구하지 고민하다, n-Sum(Sum 은 1,2,3,4,, 총합) 을 이용해서 => 몇 번째 인지 결과를 알 수 있다.

Ex) n이 5라면 limit 찾기 속에서 Sum은 6(1+2+3)일 것이고 그렇다면 분자가 홀수이며 3인 배열속에 찾는 분수가 있다는 것을 알아내고, n-Sum = -1 이고 -1을 더 해줘서 원하는 값 2/2가 나온다. 

역시 공책에 써가면서 문제를 풀어야 실수가 적어지고 문제가 잘 풀리는 것 같다.