[SWEA/python] 21425: +=

문제

✔️ D2

문제 흐름

DP 문제를 풀던 차에 본 문제라 DP로 풀 수 있겠다 생각이 든건지,
우연찮게 DP 문제를 잡은건지 알 수가 없다.

제출 페이지 양식을 따라 바로 작성해서 따로 함수로 구분되지는 않았지만, DP를 이용했다.
번갈아가면서 a += b와 b += a를 반복해줘야 두 변수가 함께 커지면서 증가 폭도 커지게 된다.
이 과정에서 덧셈의 결과를 a와 b 앞에 계수 형식으로 붙이면 패턴을 확인할 수 있다.

1, 2, 3, 5, 8, 13 ...

과 같이 증가하는데 이는 피보나치 수열이다.
한 변수가 다른 변수보다 한차례 전 수를 계수로 갖는데, 값을 커지게 하기 위해 더 큰 계수가 더 큰 수에 붙도록 지정해줘야한다.
피보나치 수열은 DP를 이용하여 구할 수 있고, 몇번째 수까지 구해야할지 알 수 없으므로 따로 저장하지 않고 두 단계의 수만 저장하여 계산했다.

코드

# +=
# dp

T = int(input())
for test_case in range(1, T + 1):
    a, b, n = map(int, input().split())
    max_val = max(a, b)
    min_val = min(a, b)
    
    val = a + b
    cnt = 1
    # fibonacci
    num1 = 1 # max_val 계수
    num2 = 1 # min_val 계수
    
    while val <= n:
        tmp = num1
        num1 += num2
        num2 = tmp
        val = num1 * max_val + num2 * min_val
        cnt += 1
    print(cnt)