MODE::CREATIVE

2193번: 이친수 (acmicpc.net)문제 해석dp를 이용한 경우의 수 찾기알고리즘 분류dp풀이arr[i][1] = arr[i - 1][0];arr[i][0] = arr[i - 1][0] + arr[i - 1][1];점화식을 이용하여 배열을 채운다코드#include #include #include using namespace std;int n;vector> arr;int main() { cin >> n; arr.resize(n + 1, vector(2)); arr[1][0] = 0; arr[1][1] = 1; for (int i = 2; i

2579번: 계단 오르기 (acmicpc.net)문제 해석dp를 이용한 최대값 찾기알고리즘 분류dp풀이점화식 dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i])를 이용해 dp배열을 채운다코드#include #include #include using namespace std;int n;vector arr;int dp[301];int main() { cin >> n; arr.resize(n + 1); for (int i = 1; i > arr[i]; } // 초기값 설정 dp[1] = arr[1]; if (n > 1) { dp[2] = arr[1] + arr[2]; } if (n > 2) { dp[3] = m..

https://www.acmicpc.net/problem/9095문제 해석dp를 이용한 경우의 수 찾기알고리즘 분류dp풀이점화식 (dp[i] = dp[i-1] + dp[i-2] + dp[i-3]) 이용해 dp배열을 채운다코드#include #include using namespace std;int dp[12];int main() { int n; dp[1] = 1; dp[2] = 2; dp[3] = 4; for(int i = 4; i > t; for (int i = 0; i > n; cout

https://www.acmicpc.net/problem/9461문제 해석파도반 수열의 점화식을 보고 dp(동적 프로그래밍)으로 풀기알고리즘 분류dp풀이그림을 보면 삼각형의 변의 길이가 늘어나는 규칙을 알 수 있음이를 점화식으로 세우고 값을 한번에 계산하면 됨dp[i] = dp[i - 2] + dp[i - 3];코드#include #include #include using namespace std;long long dp[101];void solution() { int n; cin >> n; for(int i = 4; i > t; for (int i = 0; i

https://www.acmicpc.net/problem/11727문제 해석dp(다이나믹 프로그래밍)을 이용하여 2xn의 타일을 채울수 있는 경우의 수 구하기알고리즘 분류다이나믹 프로그래밍풀이 arr[i] = (arr[i-1] + arr[i-2]*2) 라는 규칙을 찾아내 dp배열 채우기코드#include using namespace std;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; int arr[1001]; arr[1] = 1; arr[2] = 3; cin >> n; for(int i = 3; i

https://www.acmicpc.net/problem/11726 문제 해석dp(다이나믹 프로그래밍)을 이용하여 2xn의 타일을 채울수 있는 경우의 수 구하기알고리즘 분류다이나믹 프로그래밍풀이 arr[i] = (arr[i-1] + arr[i-2]) 라는 규칙을 찾아내 dp배열 채우기코드#include using namespace std;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; int arr[1001]; arr[1] = 1; arr[2] = 2; cin >> n; for(int i = 3; i