[백준] 2502번: 떡 먹는 호랑이

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

initial

Very strange question. I tried finding out the pattern via making an algebraic equation of something like 5x+3y=41, where x and y are dp[1] and dp[2]. But I thought there would be an itertools library to resolve this but nope. So i tired resolving via a double for loop where i iterate x from 1 to 100k and if there is a value of y that satisfies this equation condition, i exit out of loop. Problem is, x=1 and y=12 also meets this condition but 41 cannot be made of just 1 dp[2] and 12 dp[1] because naturally there are more or equal dp[2] than dp[1].

Oh i placed dp[2] in the inner for loop instead of outer for loop. That is why my code was wrong! It should be

For x in range(1,100001):
For y in range(1,100001):
If ay +bx==k

Instead of
For x in range(1,100001):
For y in range(1,100001):
If ax +by==k

This came from a fatal mistake that I forgot that number of dp[2] is greater or equal to dp[1].

solution

d, k = map(int, input().split())
dp = [(0, 0) for _ in range(d + 1)]
dp[1] = (0, 1)
dp[2] = (1, 0)

for i in range(3, d + 1):
    dp[i] = (dp[i - 1][0] + dp[i - 2][0], dp[i - 1][1] + dp[i - 2][1])

a, b = dp[d]

for x in range(1, 100001):
    for y in range(1, 100001):
        if a * y + b * x == k:
            print(x)
            print(y)
            break
    else:
        continue
    break

complexity

n^2 time and n space