문제 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 문제에서 주어진 코드대로 피보나치 수열을 재귀함수로 구현하고, 0과 1을 세는 방법으로 문제를 풀면 시간초과가 발생한다. 대신 DP를 이용해 피보나치 수열을 풀면 된다. 피보나치 수란 한 단계 전의 숫자와 두 단계 전의 숫자를 합한 수의 수열이다. 예를 들어 1, 1, 2, 3, 5, 8 ... 등이 피보나치 수이다. 피보나치 수를 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2]이다. 이 점화식에서 dp[n - 1] = dp[n - 2] + dp[n - 3] 이고 dp[n - 2] = dp[n - 3] + dp[n - 4]..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 N을 만들기 위한 3가지 방법은 다음과 같다. 1. N가 3으로 나누어 떨어지면, 3으로 나눈다. 2. N가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 이를 식으로 표현하면, 1. dp[n] = dp[n/3] + 1 2. dp[n] = dp[n/2] + 1 3. dp[n] = dp[n-1] + 1 이고, 3나누기 -> 2나누기 -> 1빼기의 차례대로 연산을 사용하는 횟수가 적어질 것이다. 따라서 우선 dp[n]을 dp[n-1] + 1인 경우로 저장하고, 2의 배수이면 dp[n/2] + 1, 3의 배수이면 dp[n/3] + 1 으로 계산해준다. 코드 im..

문제 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 이 문제는 이중 반복문(3의 배수 + 5의 배수의 합)으로 해결할 수도 있지만, 효율적인 풀이를 위해 그리디 알고리즘과 DP를 이용할 수 있다. - 그리디 풀이 1. N이 5의 배수라면 답은 N/5 2. N이 5의 배수가 아니라면 3kg 에 한 번 담고(cnt++, N -= 3) 다시 반복문을 실행한다. 3. N이 0보다 작아지면 답은 -1 - dp 풀이 N이라는 숫자를 만들기 위해서 (N - 3) + 3 또는 (N - 5) + 5 의 경우로 나눠 볼 수 있다...