Henzee's Archive

문제 링크       문제 분석정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.n은 1보다 크고 11보다 작은 정수이다.    문제 풀이 n이 1일 때부터 경우의 수를 구해봤다.n = 1일 때 경우의 수는 (1)로 1이다.n = 2일 때 경우의 수는 (1+1), (2)로 2이다.n = 3일 때 경우의 수는 (1+1+1), (1+2), (2+1), (3)으로 4이다.n = 4일 때 경우의 수는 (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (1+3), (3+1), (2+2)로 7이다. 위의 결과를 종합해봤을 때 dp를 경우의 수를 담는 배열이라고 생각하고,dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 라는 점화식이 유도된다...

백준 1003번 - 피보나치 함수 (실버 3)     문제 이해N번째 피보나치 수를 구할 때 0과  1이 각각 몇 번 출력되는지 구하는 문제이다.  문제 해결 방법시간 제한이 0.25초라서 재귀 함수로 풀게 되면 시간 복잡도가 O(2ⁿ)이 되므로 시간 초과가 난다.동적 프로그래밍 (DP)을 사용하면 dp 배열을 한 번만 채우면 되므로 시간 복잡도가 O(N)이 된다.따라서 DP를 이용해서 문제를 풀면 된다. 먼저, 점화식을 사용해서 0과 1이 출력된 횟수를 구해준 다음 N일 때 값을 출력하면 된다.1. dp[0][n] = fibonacci(n)을 호출했을 때 0이 호출된 횟수, dp[1][n] = fibonacci(n)을 호출했을 때 1이 호출된 횟수2. 점화식 dp[0][n] = dp[0][n - 1] ..