백준) 분수찾기

문제) https://www.acmicpc.net/problem/1193

해당 문제는 백준 8단계 일반 수학 1의 문제이다.

 

처음 문제를 봤을 때 해당 문제를 풀기위하여 배열을 만들까라는 생각을 잠시 하게 되었다.

위의 그림처럼 지그재그 형식으로 되었기에 배열을 만들고 그 좌표 값을 받아와서 출력할 생각이었다.

그러나 문제에서 나왔듯이 배열은 무한하다라고 나와있다.

즉 이걸 배열을 만들어서 그 좌표를 출력을 하기가 힘들다는 말이 된다. 또한 주어지는 변수 또한 10,000,000이하로 주어지기에 최악의 경우 시간 복잡도에 걸려 틀리게 될 수 도있다.

 

그렇다면 백준 카테고리에 나와 있듯이 수학으로 문제를 풀어야한다.

 

그러나 수학을 너무 오랜만에 해서 그런지 문제의 규칙을 찾기가 어려웠다.

N	분수
1	1/1
2, 3	1/2, 2/1
4, 5, 6	3/1, 2,2, 1/3
7, 8, 9, 10	1/4, 2/3, 3/2, 4/1
11, 12, 13, 14, 15	5/1, 4/2, 3/3, 2/4, 1/5
16, 17, 18, 19, 20, 21	1/6/ 2/5, 3/4, 4/3, 5/2, 6/1
22, 23, 24, 25, 26, 27, 28	7/1, 6/2, 5/3, 4/4, 3/5, 2/6, 1/7

 

문제의 조건을 맞춰 표로 나타내었을때 나오는 규칙이다

깊이에따라 갯수가 1개씩 증가하는 것을 알 수있으며

깊이가

짝수 일때 분모가 1증가 분자가 1감소

홀수 일때 분모가 1감소 분자가 1증가

한다는 것을 알 수 있다

 

이를 이용하여 코드를 작성했을 때 아래 처럼 되는 것을 알 수 있다.

스포주의!!

N = int(input())

line = 0
line_end_num = 0

while line_end_num < N:
    line += 1
    line_end_num += line

K = line_end_num - N

if line % 2 == 0:
    a = line - K
    b = K + 1
else:
    a = K + 1
    b = line - K

print(f'{a}/{b}')