[C++] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다.

• 똑같은 연산을 반복하지 않도록 만들어 주고 실행 시간을 줄일 수 있다.
• 작은 문제들을 풀어나가다 보면 이전에 구해둔 더 작은 문제들이 활용되는 것을 확인하게 된다. 이에 대한 규칙을 찾았을 때 점화식을 도출해 내어 동적 계획법에 적용한다.

 

풀이법

1. dp[i]가 의미하는 바
2. dp[i]를 initialize 하는 방법
3. dp[i]의 점화식
4. dp[i]를 채우는 순서
5. 정답이 의미하는 바

 

https://jyeonth.tistory.com/7

Leetcode: Word Break

 

문제

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

#include <iostream>
#include <algorithm>
using namespace std;

int dp[501][501];

int main()
{
	int n;
	cin >> n;

	int result = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++) {
			cin >> dp[i][j];
			if (j == 1) // 왼쪽 대각선
				dp[i][j] += dp[i - 1][j];
			else if (i == j) // 오른쪽 대각선
				dp[i][j] += dp[i - 1][j - 1];
			else
				dp[i][j] += max(dp[i - 1][j], dp[i - 1][j - 1]);

			if (result < dp[i][j])
				result = dp[i][j];
		}
        
	cout << result;
}

 

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1000001];

int main()
{
	int n;
	cin >> n;

	dp[1] = 0;
	for (int i = 2; i <= n; i++)	{
		dp[i] = dp[i - 1] + 1;
		if (i % 2 == 0 && dp[i / 2] + 1 <= dp[i])
			dp[i] = dp[i / 2] + 1;
		if (i % 3 == 0 && dp[i / 3] + 1 <= dp[i])
			dp[i] = dp[i / 3] + 1;
	}

	cout << dp[n];
}

 

https://www.acmicpc.net/problem/1912

1912번: 연속합

#include <iostream>
#include <algorithm>
using namespace std;

int dp[100001];

int main()
{
	int n;
	cin >> n >> dp[0];
	for (int i = 1; i < n; ++i) {
		cin >> dp[i];
		dp[i] = max(dp[i], dp[i - 1] + dp[i]);
	}

	cout << *max_element(dp, dp + n);
}

 

https://leetcode.com/problems/longest-valid-parentheses/

Longest Valid Parentheses - LeetCode

#include <vector>
#include <string>
#include <stack>
using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        int answer = 0;
        stack<int> st;
        vector<int> dp(s.size(), 0);

        for (int i = 0; i < s.size(); i++) {
            char c = s[i];
            if (c == '(')
                st.push(i);
            else {
                if (st.empty())
                    continue;

                int index = st.top();
                st.pop();
                dp[i] = i - index + 1 + (index > 0 ? dp[index - 1] : 0);
            }
            answer = max(answer, dp[i]);
        }

        return answer;
    }
};

 

문제 : 연속 값이 불가능할 때 최댓값 구하기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	cin >> n;

	int stair[300], dp[300];
	for (int i = 0; i < n; i++)
		cin >> stair[i];

	dp[0] = stair[0];
	dp[1] = stair[0] + stair[1];
	dp[2] = max(stair[1] + stair[2], stair[0] + stair[2]);
	for (int i = 3; i < n; i++)
		dp[i] = max(stair[i] + dp[i - 2], stair[i] + stair[i - 1] + dp[i - 3]);

	cout << dp[n - 1];
}

 

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	cin >> n;

	int grape[10001];
	for (int i = 1; i <= n; ++i)
		cin >> grape[i];

	int dp[10001]{};
	dp[1] = grape[1];
	dp[2] = grape[1] + grape[2];
	for (int i = 3; i <= n; ++i)
		dp[i] = max(dp[i - 1], max(dp[i - 2], dp[i - 3] + grape[i - 1]) + grape[i]);

	cout << dp[n];
}

 

문제 : LIS(최장 증가 부분 수열)

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, ans = 0;
	cin >> N;

	int A[1010]{}, dp[1010]{};
	for (int i = 1; i <= N; i++)
		cin >> A[i];

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j < i; j++)
			if (A[i] > A[j] && dp[i] < dp[j])
				dp[i] = dp[j];
		dp[i]++;
		if (ans < dp[i])
			ans = dp[i];
	}
	cout << ans;
}

 

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int N;
	cin >> N;

	vector<pair<int, int>> poles;
	int dp[100];
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		poles.push_back({ a, b });
		dp[i] = 1;
	}

	// a 전봇대의 전깃줄 위치를 기준으로 정렬
	sort(poles.begin(), poles.end());

	// a 전봇대를 기준으로 전깃줄을 정렬했을 때
	// b 전봇대도 전깃줄 순서가 정렬되어있어야 둘이 엉키지 않는다.
	for (int i = 0; i < N; i++)
		for (int j = 0; j < i; j++)
			if (poles[i].second > poles[j].second)
				dp[i] = max(dp[i], dp[j] + 1);

	// b 전봇대의 부분증가수열은 모두 정렬된 상태이므로
	// 원래 길이에서 부분증가수열의 길이를 뺀다.
	cout << N - *max_element(dp, dp + N);
}

 

문제 : LCS(최장 공통 부분 수열)

https://www.acmicpc.net/problem/9251

9251번: LCS

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int dp[1001][1001];

int main()
{
	string s1, s2;
	cin >> s1 >> s2;

	for (int i = 1; i <= s1.length(); i++)
		for (int j = 1; j <= s2.length(); j++)
			dp[i][j] = (s1[i - 1] == s2[j - 1]) ? dp[i - 1][j - 1] + 1 : max(dp[i][j - 1], dp[i - 1][j]);
	cout << dp[s1.length()][s2.length()];
}

 

문제 : 냅색

주어진 용량을 초과하지 않으면서 전체 이득이 최대가 될 수 있도록 하는 문제이다.

 

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

#include <iostream>
#include <algorithm>
using namespace std;

int dp[100001];

int main()
{
	int n, k;
	cin >> n >> k;

	while (n--) {
		int w, v;
		cin >> w >> v;
		for (int i = 0; i <= k - w; i++)
			dp[i] = max(dp[i], dp[i + w] + v);
	}

	cout << *max_element(dp, dp + k);
}

 

https://www.acmicpc.net/problem/2293

2293번: 동전 1

#include <iostream>
using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;

	int dp[10001]{ 1 };
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		for (int j = tmp; j <= k; j++)
			dp[j] += dp[j - tmp];
	}

	cout << dp[k];
}

 

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	int card[1001], dp[1001]{};
	for (int i = 1; i <= N; ++i)
		cin >> card[i];

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= i; j++)
			dp[i] = max(dp[i], dp[i - j] + card[j]);
	cout << dp[N];
}

 

문제 : 최소비용 구하기

https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

#include <iostream>
#include <algorithm>
using namespace std;

int dp[501][501];
int sum[501];

int main()
{
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; ++i) {
			cin >> sum[i];
			sum[i] += sum[i - 1];
		}

		for (int i = 1; i <= n; ++i)
			for (int start = 1; start + i <= n; ++start) {
				int end = start + i;
				dp[start][end] = 1e9;
				for (int j = start; j < end; ++j)
					dp[start][end] = min(dp[start][end], dp[start][j] + dp[j + 1][end] + sum[end] - sum[start - 1]);
			}
		cout << dp[1][n] << endl;
	}
}

 

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

#include <iostream>
#include <algorithm>
using namespace std;

int dp[501][501];
int a[501][2];

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i][0] >> a[i][1];
		if (i > 1)
			dp[i - 1][i] = a[i - 1][0] * a[i - 1][1] * a[i][1];
	}

	for (int i = 2; i <= n; i++)	// 행렬이 3개 이상일 경우
		for (int start = 1; start + i <= n; start++) {
			int end = start + i;
			dp[start][end] = 1e9;
			for (int j = start; j < end; j++)
				dp[start][end] = min(dp[start][end], dp[start][j] + dp[j + 1][end] + a[start][0] * a[j][1] * a[end][1]);
		}
	cout << dp[1][n];
}

 

https://leetcode.com/problems/dungeon-game/

#include <vector>
#include <math.h>
using namespace std;

class Solution
{
public:
    int dp[201][201]{};

    int calculateMinimumHP(vector<vector<int>>& dungeon)
    {
        int m = dungeon.size();
        int n = dungeon[0].size();

        for (int i = m - 1; i >= 0; --i) {
            for (int j = n - 1; j >= 0; --j) {
                if (i == m - 1 && j == n - 1)
                    dp[i][j] = max(1, 1 - dungeon[i][j]);
                else if (i == m - 1)
                    dp[i][j] = max(1, dp[i][j + 1] - dungeon[i][j]);
                else if (j == n - 1)
                    dp[i][j] = max(1, dp[i + 1][j] - dungeon[i][j]);
                else
                    dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
            }
        }

        return dp[0][0];
    }
};

 

문제 : DFS+DP

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

#include <iostream>
using namespace std;

int M, N;
int h[500][500], dp[500][500];
int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

int f(int y, int x, int hei)
{
	if (x < 0 || x >= N || y < 0 || y >= M || h[y][x] >= hei)
		return 0;
	else if (y == M - 1 && x == N - 1)
		return 1;
	else if (dp[y][x] >= 0)
		return dp[y][x];

	dp[y][x] = 0;
	for (int i = 0; i < 4; i++)
		dp[y][x] += f(y + dir[i][0], x + dir[i][1], h[y][x]);
	return dp[y][x];
}

int main()
{
	cin >> M >> N;
	for (int i = 0; i < M; i++)
		for (int j = 0; j < N; j++) {
			cin >> h[i][j];
			dp[i][j] = -1;
		}
	cout << f(0, 0, h[0][0] + 1);
}

 

문제 : DFS+BFS+DP

https://leetcode.com/problems/word-ladder-ii/

Word Ladder II - LeetCode

#include <vector>
#include <map>
#include <queue>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<string>> answers;
    vector<string> answer;
    bool check[500];
    map<string, int> counts;
    int minCount;

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        minCount = 0;
        queue<pair<string, int>> q;
        q.push({ beginWord, 0 });
        while (!q.empty()) {
            string word = q.front().first;
            int cnt = q.front().second;
            q.pop();

            if (word == endWord) {
                minCount = cnt;
                break;
            }

            for (int i = 0; i < wordList.size(); i++)
            {
                if (check[i] || isNearWord(word, wordList[i]) == false)
                    continue;
                check[i] = true;
                q.push({ wordList[i], cnt + 1 });
            }
        }

        memset(check, false, sizeof(check));
        answer.push_back(beginWord);
        dfs(beginWord, endWord, wordList, 0);
        return answers;
    }

    bool dfs(string& curWord, string& endWord, vector<string>& wordList, int count) {
        if (count == minCount) {
            if (curWord != endWord)
                return false;
            else {
                answers.push_back(answer);
                return true;
            }
        }
        else if (counts.find(curWord) != counts.end() && counts[curWord] <= count)
            return false;

        bool movable = false;
        for (int i = 0; i < wordList.size(); i++) {
            if (check[i] || isNearWord(curWord, wordList[i]) == false)
                continue;

            check[i] = true;
            answer.push_back(wordList[i]);
            if (dfs(wordList[i], endWord, wordList, count + 1))
                movable = true;
            answer.pop_back();
            check[i] = false;
        }

        if (movable == false)
            counts[curWord] = count;
        return movable;
    }

    bool isNearWord(string& cur, string& next) {
        int cnt = 0;
        for (int i = 0; i < cur.size(); i++)
            if (cur[i] != next[i])
                cnt++;
        return cnt == 1;
    }
};

 

문제 : left to right

https://leetcode.com/problems/candy/description/

LeetCode - The World's Leading Online Programming Learning Platform

#include <vector>
using namespace std;

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candyCount(n, 1);

        // left to right
        for (int i = 1; i < n; ++i) {
            if (ratings[i - 1] < ratings[i]) {
                candyCount[i] = candyCount[i - 1] + 1;
            }
        }

        // right to left
        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) {
                candyCount[i] = max(candyCount[i], candyCount[i + 1] + 1);
            }
        }

        int answer = 0;
        for (int i = 0; i < candyCount.size(); ++i)
            answer += candyCount[i];
        return answer;
    }
};

 

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/

LeetCode - The World's Leading Online Programming Learning Platform

#include <vector>
#include <math.h>
using namespace std;

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        vector<int> leftProfit(size, 0);
        vector<int> rightProfit(size, 0);

        int minPrice = prices[0];
        for (int i = 1; i < size; ++i) {
            minPrice = min(prices[i], minPrice);
            leftProfit[i] = max(leftProfit[i - 1], prices[i] - minPrice);
        }

        int maxPrice = prices[size - 1];
        for (int i = size - 2; i >= 0; --i) {
            maxPrice = max(prices[i], maxPrice);
            rightProfit[i] = max(rightProfit[i + 1], maxPrice - prices[i]);
        }

        int answer = 0;
        for (int i = 0; i < size; ++i)
            answer = max(answer, leftProfit[i] + rightProfit[i]);
        return answer;
    }
};