피보나치 함수 (DP, 백준 1003번)

- 문제 : https://www.acmicpc.net/problem/1003

 

1. 생각해보기

그래프를 그려보면, N = (N-1) + (N-2)를 더한 경우의 수라는 것을 알 수 있다. 

여기에서 0,1의 케이스에 대해서 각각 구해야 하는데 이는 DP 테이블에 넣어줄거다. (2차원 배열로[i][0]에는 0의 개수, [i][1]에는 1의 개수)

 

초기값은 0,1에 대해서 세팅이 필요하다 

DP[0][0] = 1

DP[0][1] = 0

DP[1][0] = 0

DP[1][1] = 1

 

// max값 가져와서 max까지 DP 테이블 채우기

for(let i=2; i<= max; i++){

     DP[i][0] = DP[i-1][0] + DP[i-2][0];

     DP[i][1] = DP[i-1][1] + DP[i-2][1];

}

 

// 출력

for(...)

 

[시간복잡도]

N의 최대값은 40개라고 했으니까. 최대 40까지 DP 테이블을 채우게 되고, 

출력은 입력개수 만큼 for문이 돌게 된다. 

시간은 0.25초임으로, 1억(10^8) * 0.25 = 25 * 10^6 계산 가능함으로 충분히 계산가능하다. 

 

 

2. 결과

 

첫번째 시도에서 런타임 에러가 발생했습니다. 

이유는 DP테이블에 초기값을 세팅해주는데 max값이 0이 오는 경우, DP[1][0]과 DP[1][1]에는 접근 할 수 없기 때문이었습니다. 

해당 부분에 if문을 걸어주는 방향으로 코드 수정을 하였더니 개선되었습니다 

 

https://github.com/moonlight-duck/study-algorithms/pull/27

[민주] DP (+ Greedy) 문제 by min-99 · Pull Request #27 · moonlight-duck/study-algorithms