목록피보나치 수열 (1)

JINWOOJUNG

[ DP - 1003 ] 피보나치 함수

접근법 처음엔 피보나치 함수의 Code가 주어졌으니, 직접 재귀함수를 실행하면서 n이 1 또는 0일 때, 조건문을 걸어 개수를 계산하려고 하였으나 역시나..시간초과! 따라서 DP문제이기에 몇가지를 시도해본 결과 왼쪽이 0이 출력되는 개수, 오른쪽이 1이 출력되는 개수이다. 즉 피보나치 함수의 재귀적인 호출 처럼 각각의 출력 개수 역시 -1, -2 번째의 출력 개수의 합으로 유도할 수 있음을 알 수 있다. 하지만 0의 경우 1,2번재 부터 유효하고, 1의 경우 0,1 부터 유효하므로 두 DP 배열의 0,1,2번째 원소는 직접 입력하고, 나머지는 반복문을 돌면서 계산하면 된다. 정답 #include #include using namespace std; int32_t st_DP0[41]; int32_t st_..
백준 2024. 3. 30. 04:00
이전 Prev 1 Next 다음