[BOJ/백준] 1139번 파이썬 해결

그림으로 이해하는게 훨씬 빠른 문제이다.

(1) 1/1	(2) 1/2	(6) 1/3	(7) 1/4	1/5	1/6
(3) 2/1	(5) 2/2	(8) 2/3	2/4	2/5	...
(4) 3/1	(9) 3/2	3/3	3/4	...	...
(10) 4/1	4/2	4/3	...	...	...
5/1	5/2	...	...	...	...
6/1	...	...	...	...	...

1이 입력으로 주어지면 1/1, 2가 주어지면 1/2, 3이 주어지면 2/1, 4는 3/1, 5는 2/2 ...

---

나는 수학에 매우 약해서 문제를 거의 혼자 해결하지 못했다.

 

문제를 해결하기 위해선 '입력으로 주어진 수(이하 x)가 몇 번 대각선(이하 line)인가?'를 생각해야한다.

1 = 1

2, 3 = 2

4, 5, 6 = 3

7, 8, 9, 10 = 4

...

이 후에는 1부터 line까지를 더한다.

1 = 1

2 = 3

3 = 6

4 = 10

여기서 알 수 있는 사실은 x는 절대 line까지의 합을 절대 넘지 않는다.

나아가서는 전 line까지의 합을 x에 빼면 분자 또는 분모를 구할 수 있다.

x = int(input())

line = 1

while x < sum_line :
    x -= line
    line += 1

그럼 이제 홀수 line인지, 짝수 line인지에 따라 분자, 분모의 값을 바꿔주면 된다.

왜 line의 홀짝에 따라서 값을 바꾸냐면, 홀수 라인에서는 위로 올라가면서 분자는 1씩 빼주고 분모는 1씩 더하며, 반대로 짝수라인은 아래로 내려가면서 분자는 빼주고 분모는 더하기 때문이다.

x = int(input())

line = 1

while x < sum_line :
    x -= line
    line += 1

numerator = x # 분자 +1
denominator = line - x + 1 # 분모 -1

if line & 1 :
    denominator, numerator = numerator, denominator

print(f"{numerator}/{denominator}")