[SWEA] <D2> 21425 - += (Python)

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AZD8K_UayDoDFAVs

SW Expert Academy

문제

C, C++, Python, Java 등의 언어에는 += 연산자가 있다. 정수형 변수 x, y가 있을 때 “x += y”를 하면 x에 저장된 값이 (기존에 x에 저장되어 있던 값) + (기존에 y에 저장되어 있던 값)으로 바뀐다.
현재 x에 저장된 값은 A, y에 저장된 값은 B이다. 당신은 “x += y” 또는 “y += x” 연산을 원하는 순서대로 원하는 만큼 수행하여, x나 y 둘 중 하나 이상에 저장된 값이 N 초과가 되게 하려고 한다. 연산을 합쳐서 최소 몇 번 수행해야 하는지 계산하는 프로그램을 작성하라.

---

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 한 개의 줄로 이루어진다. 각 줄에는 세 개의 정수 이 공백 하나씩을 사이로 두고 주어진다.

테스트 케이스의 개수는 600,000개 이상으로 상당히 많음에 유의하라.

출력

각 테스트 케이스마다, 한 줄에 하나씩 x나 y 둘 중 하나 이상에 저장된 값이 N 초과가 되게 하기 위해 “x += y”, “y += x” 연산을 최소 몇 번 수행해야 하는지 출력한다.

---

예제 입력 

5
1 2 2
1 2 3
1 2 4
1 2 5
10 7 1293

예제 출력

1
2
2
3
11

---

해결 방법

처음 문제를 봤을 때 연산을 수행하는 방법은 크게 두가지 생각났다. 

1. 작은쪽에 큰 수를 더해주기
2. 큰쪽에 작은 수를 더해주기

물론 생각을 해보면 1번이 둘 중 하나라도 N을 초과하게 만들기에 합당한 방법임을 알 수 있다.

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    a,b,n = map(int,input().split())
    cnt = 0
    while ( a <= n or b <= n):
        if a > b:
            b += a
        else:
            a += b
        cnt += 1
    print(cnt-1)