나한나한나한나

문제 : 백준 1003번

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

---

 

첫 접근 : dp_list를 0부터 40까지 미리 채워두면 되는 것 아닌가?

문제에 나온 예시처럼 재귀함수를 열라게 돌려서 dp_list를 채우도록 해 봤다.

dp_list = [[] for _ in range(41)]
count_0 = 0
count_1 = 0


def fibonacci(n):
    global count_0, count_1
    if (n == 0) :
        count_0 += 1
        return 0
    elif (n == 1):
        count_1 += 1
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

def counting(n):
    fibonacci(n)
    return [count_0, count_1]         

for i in range(41):
    count_0 = 0
    count_1 = 0
    res = counting(i)    
    dp_list[i] = res  

print(dp_list)  



T = int(input())
N = [int(input()) for _ in range(T)]
for i in N:
    res = dp_list[i]
    print(f"{res[0]} {res[1]}")

개오래걸림 당연히 시간초과

---

두번째 접근 : 꼼수

터미널을 쳐다보면서 머리를 굴려보니 아니, 계산 결과가 다 나와있는 거 아닌가?

그럼 뭐하러 계산함? 그냥 때려박고 돌리면 되지

dp_list = [[1, 0], [0, 1], [1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 13], [13, 21], [21, 34], [34, 55], [55, 89], [89, 144], [144, 233], [233, 377], [377, 610], [610, 987], [987, 1597], [1597, 2584], [2584, 4181], [4181, 6765], [6765, 10946], [10946, 17711], [17711, 28657], [28657, 46368], [46368, 75025], [75025, 121393], [121393, 196418], [196418, 317811], [317811, 514229], [514229, 832040], [832040, 1346269], [1346269, 2178309], [2178309, 3524578], [3524578, 5702887], [5702887, 9227465], [9227465, 14930352], [14930352, 24157817], [24157817, 39088169], [39088169, 63245986], [63245986, 102334155]]

T = int(input())
N = [int(input()) for _ in range(T)]
for i in N:
    res = dp_list[i]
    print(f"{res[0]} {res[1]}")

통과는 했지만 알고 있다. 이딴식으로 풀면 안된다는 것을...

---

세번째 접근 : 어라? index 0이랑 index 1 끼리 피보나치네?

꼼수로 통과한 코드를 가만 보니 index 0이랑 index 1끼리도 피보나치가 성립하는 게 아닌가?

앞에놈들끼리만 계산하고 뒤에놈들끼리만 계산하면 재귀 돌릴 필요도 없는 것 아닌가 하는 생각이 들어 돌려봤다

dp_list = [[] for _ in range(41)]
dp_list[0] = [1,0]
dp_list[1] = [0,1]
dp_list[2] = [1,1]
# print(dp_list)

for i in range(3,41):
    dp_list[i] = [dp_list[i-1][0] + dp_list[i-2][0] , dp_list[i-1][1] + dp_list[i-2][1]]
    
# print(dp_list)

T = int(input())
N = [int(input()) for _ in range(T)]
for i in N:
    res = dp_list[i]
    print(f"{res[0]} {res[1]}")

역시나 결과가 개빠르게 나온다. 제출했고, 통과했다.

꼼수가 힌트를 주다니 세상메 마상에.

---

결론 : 잔머리도 도움이 될 때가 있다