다이나믹 프로그래밍4 효율성 - 최대 부분 배열 합, 두 퀸 1. NP - hard 문제 : 다항시간 알고리즘이 알려지지 않은 문제 2. 최대 부분 배열 합 배열에서 연속해 있는 값들을 선택해서 그 합을 최대로 만든다면 그 합은 얼마인가? 예) -1 2 4 -3 5 2 -5 2가 입력된다면 idx : 1~5까지의 합인 10이 정답임. f(n) = n번 인덱스에서 끝나는 최대 부분 배열 합 이 점화식을 구현하면, #include #include using namespace std; const int IMP = -1e9; int main() { int n, a[10]; cin >> n; for (int i = 0; i > a[i]; int sum = a[0], best = IMP; for (int i = 1; i < n; i++) { sum.. 2019. 12. 18. Educational round #73 D - Make the fence great again (dp) https://codeforces.com/contest/1221/problem/D 한 부분 당 최대 2만큼 늘릴 수 있다는 것을 가정하고 dp모양은 만들었지만 예외가 있을 거라 생각하고 삽질함.. i==0일 떈 그냥 0~2번 다 확인해주고 i>0 일 떈 i-1의 상태와만 비교해주고 인자로 본인이 얼마나 늘렸는지만 같이 넘겨주면 된다. #include #include using namespace std; typedef long long ll; const ll MAX = 3e5 + 1; const ll INF = 1e18 + 1; int n; ll dp[MAX][3]; int h[MAX], c[MAX]; ll f(int k, int x) { if (k == n) return 0; ll& ret = dp[k].. 2019. 11. 7. BOJ 10835 - 카드게임 ( 2015 KOI 초등, dp ) https://www.acmicpc.net/problem/10835 왼쪽 더미 i번째, 오른쪽 더미 j번째를 보고 있을 때 다음으로 선택할 수 있는 경우의 수가 최대 3가지 이다. bfs로 풀어야되나? 싶었는데 i,j 외에 여태 얻은 값을 세번째 상태로 계속 넘겨줘야 해서 visited공간이 부족하고, map으로 구현하기도 비효율적이다. dp로 풀기로 해서 점화식을 짜 봤는데 깔끔하게 짜 졌다. 이후 코드로 옮기기만 했다. #include #include using namespace std; int n, a[2000], b[2000], dp[2000][2000]; int f(int i, int j) { if (i == n || j == n) return 0; int& ret = dp[i][j]; if (.. 2019. 10. 14. BOJ 1351 - 무한 수열 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 개인적으로 매우 신박한 문제다. 대놓고 기본 dp문제인데 dp배열로 풀기엔 배열 크기가 오버된다. map을 사용해서 dp하는 문제다. #include #include #include using namespace std; map dp; long long n, p, q; long long f(long long n) { if (n == 0)return 1; auto ret = dp.find(n); if (ret != dp.end()) return ret->second; long long rst = 0; rst = f(n / p) + f(n / .. 2019. 8. 6. 이전 1 다음
