::SemiColon;;

1. 문제 https://www.acmicpc.net/problem/9461 2. 풀이 문제에서 P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이라고 하였다. 위의 수열을 보면 P(i) = P(i-2) + P(i-3)이라는 것을 알 수 있다. 이를 통해 코딩을 하면된다. 3. 소스코드 #include using namespace std; int t, n, mxn = 3; long long dp[101]; int main() { ios::sync_with_stdio(0); cin.tie(), cout.tie(); dp[1] = dp[2] = dp[3] = 1; cin >> t; while (t--) { cin >> n; if (mxn < n) { for (..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이번문제는 dp(다이나믹 프로그래밍)를 이용하여 푸는 문제이다. 예시들을 쭉 세워보면 n = 1은 0, n = 2는 1, n = 3은 1, n = 4는 2, n = 5는 3, n = 6은 2 이다. 위의 예시들 중 n = 6을 보면 6은 3으로도 나누어 떨어지고, 2로도 나누어 떨어진다. 따라서 6을 3으로 나눈값, 2로 나눈값, 1을 뺸값을 다 비교해보아야한다. 즉 dp[6] = min(dp[6/3], dp[6/2], dp[6-1])이다. 이를 토대로 점화식을 세워보면 dp[i] = min(dp[i/3] (i..

https://www.acmicpc.net/problem/1149 기본적인 DP문제입니다. 문제를 푸는 아이디어는 집을 색칠할 수 있는 3가지 색깔의 경우의수를 모두다 구해보는 것입니다. 코드로는 for (int i = 1; i < N; i++) { dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][0]; dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + input[i][1]; dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + input[i][2]; } 이렇게 될것입니다. dp[i][j]는 i번째 집을 j색깔로 칠했을때의 최소비용입니다. 따라서 dp[i][0]은 i번째 집을 0번 페인트로 칠했을때 ..