코후닝

알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 【 풀이 】 피보나치 함수의 호출 횟수를 출력하는 문제이다. 문제의 코드에 호출될 때마다 횟수를 더해주는 코드를 작성해서 그 횟수를 출력하면 당연히 시간 복잡도에 걸려 시간 초과가 발생하게 된다. 하지만 그 횟수 출력으로 우리가 따로 횟수를 확인해 규칙을 찾고 점화식을 도출해 동적계획법으로 해결하면 된다. 규칙을 찾아본 결과 n[0] = 1 n[1]..