정화 코딩

https://www.acmicpc.net/problem/11054 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(n); for (int i = 0; i > a[i]; vector dp1(n); vector dp2(n); for (int i = 0; i a[j]) maxt = max(maxt, dp1[j]); } dp1[i] = maxt + 1; } for (int i = n - 1; i >= 0; i--) { in..

9회차 - dp  피보나치 수 2https://www.acmicpc.net/problem/2748피보나치 수를 구하는 걸 재귀로 구현하게 되면 시간 복잡도가 O(2^n)이므로 n이 조금만 커져도 실행 시간이 기하급수적으로 늘어나게 됩니다. 이는 같은 피보나치 값을 여러 번 중복 계산하기 때문입니다. 예를 들어, fib(5)를 계산할 때 fib(3)이 두 번, fib(2)가 세 번 호출되는 식으로 불필요한 연산이 계속 발생합니다.따라서 중복 계산을 막기 위해 이전에 계산한 값들을 저장하고 활용해야 합니다. 이럴 때 사용하는 대표적인 방법이 동적 계획법(DP)를 사용하게 되는 것입니다.#include #include using namespace std;int main() { ios_base::sync_..

https://www.acmicpc.net/problem/11048 #include #include #include using namespace std;int dx[3] = {1, 0, 1};int dy[3] = {0, 1, 1};vector> a;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; a = vector>(n, vector(m)); for (int i = 0; i > a[i][j]; } } queue> q; q.push({0, 0, a[0][0]}); int ans = 0; while (!q.empty..

https://www.acmicpc.net/problem/2096 #include #include using namespace std;int const INTMAX = 1000000000;int const MAX_N = 100000;int m[MAX_N][3];int dpmax[2][3];int dpmin[2][3];int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i > m[i][j]; } } for (int j = 0; j 처음에는 dp 배열을 n * 3으로 선언했었는데 메모리 초과가 났었다. (MLE) 생각해보니 d..

https://www.acmicpc.net/problem/17404 #include #include using namespace std;int MAXV = 1000 * 1000 + 1;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector> rgb(n + 1, vector(3)); for (int i = 1; i > rgb[i][j]; } } vector> dp(n + 1, vector(3)); int ans = MAXV; // 첫번째 집이 각각 r, g, b일 때로 나눠서 dp 채우기 for (int first = 0;..

https://www.acmicpc.net/problem/10942 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n; vector a(n); vector> dp(n, vector(n, 0)); for (int i = 0; i > a[i]; dp[i][i] = 1; if (i == 0) continue; if (a[i] == a[i - 1]) dp[i - 1][i] = 1; } for (int i = 0; i > m; while (m--)..

https://www.acmicpc.net/problem/17626 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector dp(n + 1, 100); dp[0] = 0; dp[1] = 1; for (int i = 1; i "최소" 개수의 제곱수 합으로 표현해야 한다는 점에서 dp가 떠올랐다. 0부터 n까지 배열로 만들고 제곱수를 더해가며 dp 배열을 채웠다. (AC)

https://www.acmicpc.net/problem/11727 #include #include using namespace std;int mod = 10007;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector dp(n + 1, 0); dp[1] = 1; if (n > 1) dp[2] = 3; for (int i = 3; i 점화식: dp[n] = (2 * dp[n - 2] + dp[n - 1]) % mod(n - 2)까지 채운 것에 1 * 2 타일 2개 또는 2 * 2 타일 1개 붙이기 + (n - 1)까지 채운 것에 1 * 2 타일 1개..