백준 1193번 문제 풀이 - 공부하는 도비

www.acmicpc.net/problem/1193

1193번: 분수찾기

 

첫 번째 표를 대각선으로 한 줄씩 끊으면, 바로 위와 같은 표를 완성할 수 있습니다.

가만히 저 표를 보면, 홀수 번째 방의 데이터 양상은 아래와 같다는 걸 알 수 있습니다.

 

홀수 방의 데이터 양상

반대로, 짝수 방의 데이터 양상은 아래와 같습니다.

짝수 방의 데이터 양상

위에서 설명한 부분은 코드의 마지막 if 절에 해당합니다. 

마지막에 홀수 방과 짝수 방을 따로 처리하는 거죠.

import sys
num = int(sys.stdin.readline())     

tmp = num                           
count = 0     
                      
while tmp > 0:
    count += 1
    tmp -= count

arr = list(range(1, count+1))

p = count + tmp - 1
brr = arr[::-1]

if (count) % 2 != 1:
    print("%d/%d" %(arr[p],brr[p]))
else:
    print("%d/%d" %(brr[p],arr[p]))

우선 num 변수에 정수 하나를 입력받고, 

tmp 변수에 저장합니다. (글을 쓸 때 보니 굳이 tmp에 따로 저장하지 않고 num 변수를 계속 써도 되네요 ㅎ)

 

이 문제에서 가장 중요한 부분을 담당하는 while 절입니다.

 

제가 위에서 계속 몇 번째 방, 홀수, 짝수 방이란 말을 했는데 

입력된 정수에 대해 그 방을 정해주는 부분입니다.!!

 

Ex) num(=tmp) = 12, 아래 표를 만들 수 있습니다.

12는 5번째 방에 속하게 되고, 

 

arr 배열은 count = 5이면, 1~5까지의 값이 들어간 배열을 뜻합니다.

분수의 분모 또는 분자로 사용하기 위해서죠.

 

또 여기서 중요한 계산이 나옵니다.

 

변수 p는 

count와 tmp를 더한 뒤, 1을 추가적으로 빼주면, 12라는 수가 어디에 위치되어있는지 알려주는 역할을 합니다.

[ [1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15] .. ]

5번째 방에 있고, 배열로서는 첫 번째 순서에 위치하네요.

 

p와 arr, brr배열을 이용하면, 분수로 매칭 시키는 건 간단해집니다.

 

 

추가로, 문제의 입력 예시 범위가 1부터 10,000,000이기 때문에

배열을 선언하고, 입력된 값까지 수를 저장하면서 문제를 풀게 되면 시간 초과가 날 수 있는 문제이니

유의하시면 좋을 거 같습니다.!