목록다이나믹 프로그래밍 (63)

1일1알

백준 2631번 줄세우기 C++

전체 아이들의 수에서 가장 긴 증가하는 부분 수열의 수를 빼면 된다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector v(n); for (int i = 0; i > v[i]; } vector dp(n, 1); int max_length = 0; ..
알고리즘 2022. 3. 12. 15:50
백준 2748번 피보나치 수 2 C++

dp[ i ] = dp[ i - 2 ] + dp[ i - 1 ] , int 범위를 넘어가기 때문에 long long으로 선언하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector dp(91, 0); dp[1] = 1; int n; cin >> n; for (int i = 2; i
알고리즘 2022. 2. 26. 11:09
백준 11066번 파일 합치기 C++

i~j의 최소비용은 i ~ m - 1 의 비용 + m ~ j 의 비용 중 제일 작은 값이다. (m은 i ~ j 사이의 값) 문제를 풀면서 여기까지는 접근했는데 합을 더해주는 부분을 생각하지 못해서 조금 헤맨 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; const int INF = 987654321; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ve..
알고리즘 2022. 2. 23. 13:31
백준 23029번 시식 코너는 나의 것 C++

세 가지 경우로 나눠서 점화식을 세웠다. 1. 세 칸 전에서 먹은 최대 음식 + 한칸 전에서 먹기 + 지금 칸에서 먹기 2. 두 칸 전에서 먹은 최대 음식 + 지금 칸에서 먹기 3. 한 칸 전에서 먹은 최대 음식, 지금 칸에선 안먹기 max(dp[i - 3] + v[i - 1] + v[i] / 2, dp[i - 2] + v[i], dp[i - 1]) #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with..
알고리즘 2022. 2. 22. 12:28
백준 9252번 LCS 2 C++

LCS 풀이는 검색해보면 좋은 설명들이 많이 있다. dp배열과 추가로 문자열을 담는 배열을 만들어서 그 배열에 문자열들을 저장했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string str1, str2; cin >> str1 >> str2; vector dp(str1.length() + 1, vector(s..
알고리즘 2022. 2. 21. 14:49
백준 11722번 가장 긴 감소하는 부분 수열 C++

일단 자기 자신만 있어도 하나의 수열이기 때문에 dp배열의 값을 전부 1로 초기화해주었다. 그리고 2중 for문을 사용했다. 첫 번째 for문은 i = 0부터 n-1까지 순차적으로 탐색하는 것이고, 두 번째 for문은 j =0부터 i - 1까지 v[j]의 값이 v[i]보다 작다면 감소하는 부분 수열이기 때문에 이전 dp[i]와 비교해서 dp[j]+1가 크다면 갱신해주는 방식으로 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int m..
알고리즘 2022. 2. 20. 12:08
이전 Prev 1 2 3 4 5 6 7 8 ··· 11 Next 다음