문제 설명 제한 사항 및 입출력 예제 개념 피보나치 수를 나눈 나머지를 구하는 문제다. 일반적인 재귀 함수 방식으로 피보나치 수열을 구해서 계산하면 같은 값을 여러 번 계산하게 되기 때문에 높은 확률로 시간 초과가 걸린다. 따라서 소수를 구할 때 에라토스테네스의 체 방식으로 미리 값들을 구해놓은 것처럼, 피보나치 수도 미리 구해놓고 계산하는 다이나믹 프로그래밍 방식을 채용하면 문제를 효율적으로 해결할 수 있다. 풀이 #include using namespace std; int solution(int n) { vector dp(n + 1, 0); dp[0] = 0; dp[1] = 1; for (int i = 2; i
