[python] 백준 1193 : 분수 찾기

[python] 백준 1193 : 분수 찾기

1193번: 분수찾기

난이도 : 브론즈 1

분류 : 수학, 구현

---

코드

X = int(input())
line = 0
end = 0

while end < X:
    line += 1
    end += line

gap = end - X
mom = 1
son = 1

if line % 2 == 0:
    son = line - gap
    mom += gap
else:
    son += gap
    mom = line - gap
    
print(f'{son}/{mom}')

 

접근 방법

 

'이게 왜 브론즈?'라는 생각이 들 정도로 어려웠던 문제였습니다. 2시간 가까이 삽질하다가 가까스로 풀었네요.

 

문제에서 주어진 표를 순서대로 번호를 매기면 다음과 같습니다.

 

 

[1], [2, 3], [4, 5, 6], [7, 8, 9, 10]...

이런 형태로 대각선 라인이 구분됨을 알 수 있습니다.

즉, n번째 라인마다 n개의 원소가 있는 셈인데요, 이를 다시 그림으로 나타내면 다음과 같습니다.

 

1번 라인 [1]

2번 라인 [2, 3]

3번 라인 [4, 5, 6]... 과 같은 형태로 구분되고 있습니다.

 

자세히 살펴보시면 번호가 증가함에 따라

홀수 라인(파란 선) : 분자는 감소 분모는 증가

짝수 라인(빨간 선) : 분자는 증가 분모는 감소

와 같은 방식으로 구분되어 있는 것을 발견할 수 있습니다.

 

뿐만 아니라 각 라인의 가장 큰 숫자의 분수는 다음과 같은 규칙을 보입니다.

홀수 라인(파란 선) : 분자 = 1, 분모 = 라인 번호

짝수 라인(빨간 선) : 분자 = 라인 번호, 분모 = 1

 

 

숫자의 입력을 받는 변수를 X라고 할 때 X = 8이라고 가정합니다.

8은 위의 그림에 따르면 4번째 라인에 존재하며, 짝수 라인이므로 4번 라인의 가장 큰 숫자인 10은 4/1이라는 분모를 가지게 됩니다.

짝수 라인은 숫자가 커질수록 분자는 증가, 분모는 감소하고 있다고 했습니다. 이것을 반대로 한번 적용해 봅니다.

10과 8의 차를 gap이라고 합시다. (2)

10이 가지고 있는 분모가 4/1이었으니, 분자에는 gap만큼을 빼고 분모에는 gap만큼을 더하면 8이 가지고 있는 분수인 2/3을 구할 수 있습니다.

 

따라서 X가 위치하는 라인이 몇 번째인지, 해당 라인의 가장 큰 수와 X의 차인 gap이 무엇인지, 해당 라인의 가장 큰 수가 가진 분수 값이 무엇인지를 구하면 입력한 X값이 가지는 분수를 바로 알아낼 수 있게 됩니다.

 

 

먼저 입력한 값이 몇 번째 라인에 위치하는지 알아내는 코드는 다음과 같습니다.

X = int(input())

line = 0
end = 0
while end < X:
    line += 1
    end += line
print(f'line = {line}, end = {end}')

>> 5
line = 3, end = 6

라인 별로 순서대로 번호를 매기면 다음과 같습니다. 매 라인의 가장 큰 값을 end라고 했을 때

end는 1, 3, 6, 10의 값을 가질 수 있습니다.

매 반복마다 line을 1 증가시킨 값을 end에 더하는 방법으로 이를 구현했습니다. end값이 입력한 정수 X를 넘어버리면 더 이상 반복문이 돌아가지 않으므로 X가 위치한 라인이 몇 번째 줄인 지를 구할 수 있습니다.

 

gap = end - X
mom = 1
son = 1

if line % 2 == 0:
    son = line - gap
    mom += gap
else:
    son += gap
    mom = line - gap

 

gap은 라인의 가장 큰 번호에서 입력한 정수 X의 차입니다.

mom은 분모, son은 분자와 같습니다.

 

end의 분수에서 gap만큼을 분자와 분모에 더하거나 빼주거나 하면 X의 분모를 구할 수 있습니다.

각 라인의 가장 큰 숫자의 분수는 다음과 같은 규칙을 보입니다.

홀수 라인(파란 선) : 분자 = 1, 분모 = 라인 번호

짝수 라인(빨간 선) : 분자 = 라인 번호, 분모 = 1

여기서 gap만큼을 더하거나 빼면 반복문을 쓰지 않고도 X의 분수를 구할 수 있습니다.

 

print(f'{son}/{mom}')

 

마지막으로 문자열 포맷팅 기법을 활용하여 분수를 출력하도록 했습니다.