[Python] 17504번 제리와 톰 2

https://www.acmicpc.net/problem/17504

17504번: 제리와 톰 2

---

 

24/01/24

 

 

수학에 구현을 덧붙인 재미있는 문제다. 말로는 설명하기 힘들어 예시를 하나 직접 따라가 보면 쉽게 이해할 수 있다.

---

 

문제 접근 방식:

 

 

제리가 훔쳐간 치즈의 무게만 구하면 톰이 가지고 있는 치즈의 무게를 구할 수 있다.

 

$a_1, a_2, a_3, a_4$가 각각 $2, 7, 1, 8$인 경우를 보자.

 

$$\cfrac{1}{2 + \cfrac{1}{7 + \cfrac{1}{1 + \cfrac{1}{8}}}}$$

 

편의 상 가장 안쪽에 있는 분자 $1$을 $a_5$라고 간주해 보자.

 

이후 가장 안쪽의 분수를 다음과 같이 변경할 수 있다.

 

$$\cfrac{1}{2 + \cfrac{1}{7 + \cfrac{8}{9}}}$$

 

즉, $2, 7, 1, 8, 1$이 $2, 7, 9, 8$이 됨을 확인할 수 있다.

 

여기서, $9$는 $a_3 \times a_4 + a_5$의 결과이고, $8$은 $a_4$를 그대로 가져온 것이다.

 

가장 안쪽의 분수를 변경하는 것은 이 과정의 반복이라고 할 수 있으므로, $a_1, a_2, \cdots , a_N, 1$에서 시작된 리스트에서 $3$개의 숫자를 빼고 $2$개의 숫자를 넣는, 이 과정을 반복하면 결국 연분수를 하나의 분수로 고칠 수 있을 것이다.

 

즉, 남은 두 개의 숫자 $a_0, a_1$이 분모와 분자가 되는 것이다.

 

이를 통해 제리가 훔쳐간 치즈의 무게를 구할 수 있으며, 이를 통해 톰이 가지고 있는 치즈의 무게를 구할 수 있다.

      

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 17504번 제리와 톰 2
# 수학, 구현
N = int(input())
A = list(map(int, input().split()))
A.append(1)
while len(A) >= 3:
    a = A.pop()
    b = A.pop()
    c = A.pop()
    A.append(b*c + a)
    A.append(b)
print(A[0]-A[1], A[0])