[백준 1193번-파이썬/Python] 분수 찾기

http://acmicpc.net/problem/1193

{코드}

n = int(input())
i = 0
while True:
	i += 1
	n -= i
	if n <= 0:
		n += i
		i += 1
		break
if i%2==0:
	print((i-n), '/', n, sep='')
else:
	print(n, '/', (i-n), sep='')

{설명}

문제를 보면 대각선을 하나의 그룹으로 생각하면 분수의 분모와 분자의 합이 같은 그룹 내에서는 같다는 것을 알 수 있습니다.

또한, 그룹의 분수의 수는 1씩 일정하게 증가하고 있다는 것을 알 수 있습니다.

그리고 분수의 분자는 몇번째 그룹이냐에 따라 짝수번째라면 분자가, 홀수번째라면 분모가 그룹 내에서 몇 번째 분수인지 가리킵니다.

이를 통해 분모와 분자를 구할 수 있습니다.

입력받은 N에서 i로 1, 2, 3...을 차례대로 0보다 작거나 같을 때까지 빼면 해당 그룹이 몇 번째 그룹인지 알 수 있습니다.

그런데 그룹의 분수의 분모와 분자의 합은 그룹의 번호보다 1 크므로 i를 1 증가시키고 N은 0보다 작거나 같은 수가 되기 직전의 수로 되돌립니다.

그러면 i는 그룹의 분모와 분자의 합, N은 그룹에서 몇번째 수인지 알 수 있습니다.(밑에 예시와 추가 설명)

이를 통해 만약 i가 짝수라면 N을 분자에, i-N은 분모에 넣고, 홀수라면 분자에 i-N, 분모에는 N을 넣어 출력합니다.

예시 - N이 14일 때, 답은 2/4

N	i	N - i	결과
14	1	14 - 1	13
13	2	13 - 2	11
11	3	11 - 3	8
8	4	8 - 4	4
4	5	4 - 5	-1 (while문 탈출)

이와 같이 i는 5에서 N이 0 이하가 되고 i는 1 증가한 6이 되고 N은 4가 되어 나옵니다.

이때 N은 그룹 안에서 몇 번째 분수인지를 나타내므로 4번째 분수라는 것을 알 수 있습니다.

현재 i는 짝수이므로 몇 번째인지는 분모가 나타내므로 분모는 4, 분자는 i-N인 2라는 것을 알 수 있고 이는 답과 같습니다.

예시 - N이 9일 때, 답은 3/2

N	i	N - i	결과
9	1	9 - 1	8
8	2	8 - 2	6
6	3	6 - 3	3
3	4	3 - 4	-1 (while문 탈출)

i는 5, N은 3이고 i가 홀수이므로 분자가 3, 분모가 5-3인 2이다. 답은 3/2가 된다.