이번 주 알고리즘 강의 영상도 DP인데 아주 잘 됐다! 어린이날에도 문풀하는 나는 착한 코린이 😎

Dynamic Programming

재귀: n=0, 1일 때는 직접 구하고, 나머지 step에서는 n-1 이하의 값들은 모두 계산돼 있다고 믿고 n일 때에 대해 계산을 하는 것
재귀는 느리므로 그걸 빠르게 계산하는 과정이 DP이다.
안 배우면 못 푼다. 배워야 풀 수 있고, DP 문제가 많다!

Codeforces 189A: Cut Ribbon

문제

길이가 n인 리본을 자르고 싶다. 리본을 자르는 데는 두 가지 규칙이 있다.

자른 후 각 리본 조각의 길이는 a, b, 또는 c이다.
자른 후 리본 조각의 수가 최대가 되어야 한다.

Idea

조건을 보면 greedy하게 풀 수 없다는 것을 알 수 있다. 만약 2, 3이면? 4는 2, 2로 만들 수 있지만 5는 2, 3으로밖에 나눌 수 없기 때문이다.

그 대신 모든 경우를 다 따지는 것이 가능하다. 그리고 DP 스타일로 모든 경우를 다 따지면 동일한 계산을 하지 않아도 되므로 계산이 빨라진다. 전형적인 DP 문제임.

리본을 놓고 왼쪽부터 시작해보자. 마지막 piece의 길이는 모르지만 a, b, c 중 하나이다. 그럼 세 가지 경우에 대해 다 계산해보는 것이다!

만약 a라면 이제 길이가 n-a인 리본을, b라면 길이가 n-b인 리본을, 그리고 c라면 길이가 n-c인 리본을 자르면 된다. 그리고 계산이 끝난 후 셋 중에서 가장 좋은 답을 고르면 된다.

그럼 길이가 n-a, n-b, n-c인 리본은?

계산이 되어 있다고 믿으면 된다.

Implementation

Input

최초의 리본 길이 n과 a, b, c가 순서대로 입력. 모두 1 이상 4000 이하의 자연수이므로 int로 선언하고, a, b, c는 같은 숫자일 수 있다.

Output

가능한 최대 리본 조각의 수. n이 4000이고 a, b, c 모두 1일 때 4000이 최댓값이다.

Code

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

int dp[4001][3]; // dp[i][j]: 길이가 i인 리본을 자르는데 마지막 리본의 길이가 j일 때, 리본의 최대 개수

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

	int N, a, b, c, i, tmp;
	cin >> N >> a >> b >> c;

	dp[0][0] = dp[0][1] = dp[0][2] = 0;
	for (i = 1; i <= N; i++) {
		if (i - a < 0) dp[i][0] = 0;
		else if (i - a == 0) dp[i][0] = 1;
		else { // i - a > 0
			tmp = max(dp[i - a][0], max(dp[i - a][1], dp[i - a][2]));
			dp[i][0] = (tmp == 0) ? 0 : tmp + 1;
		}
		//		cout << "dp[" << i << "][0]: " << dp[i][0];

		if (i - b < 0) dp[i][1] = 0;
		else if (i - b == 0) dp[i][1] = 1;
		else { // i - b > 0
			tmp = max(dp[i - b][0], max(dp[i - b][1], dp[i - b][2]));
			dp[i][1] = (tmp == 0) ? 0 : tmp + 1;
		}
		//		cout << " dp[" << i << "][1]: " << dp[i][1];

		if (i - c < 0) dp[i][2] = 0;
		else if (i - c == 0) dp[i][2] = 1;
		else { // i - c > 0
			tmp = max(dp[i - c][0], max(dp[i - c][1], dp[i - c][2]));
			dp[i][2] = (tmp == 0) ? 0 : tmp + 1;
		}
		//		cout << " dp[" << i << "][2]: " << dp[i][2] << endl;
	}
	cout << max(dp[N][0], max(dp[N][1], dp[N][2])) << endl;
	//	system("pause");
	return 0;
}

Codeforces 455A: Boredom

문제

n개짜리 sequence a에서 ak라는 원소를 한 번에 하나씩 뽑아 삭제할 때, 시퀀스에서 (ak)+1이나 (ak)-1의 값을 갖는 원소들도 함께 삭제할 수 있다. 이때 ak점을 얻게 되는데, 가능한 점수의 최고점을 구하라.

Idea

예를 들어 4 5 6이라는 sequence가 있다고 하자. 그러면 뽑을 수 있는 원소는 4, 5, 6 세 가지가 있다. 4를 뽑을 경우 시퀀스에서 4-1=3과 4+1=5를, 5를 뽑을 경우에는, 시퀀스에서 5-1=4와 5+1=6을, 그리고 6을 뽑을 경우에는 6-1=5와 6+1=7을 찾는다.

그런데 5의 경우 4를 뽑을 때 4+1이므로 찾았는데 6을 뽑았을 때에도 6-1이므로 시퀀스에서 찾는다. 이것으로부터 우리는 한 방향만 계산하면 된다는 것을 알 수 있다.

그럼 이제 전체 시퀀스를 소팅한 다음 문제를 풀면 된다!

Implementation

Input

시퀀스의 길이 n과 시퀀스의 원소들

Output

가능한 최대 리본 조각의 수. n이 4000이고 a, b, c 모두 1일 때 4000이 최댓값이다.

Code

// Codeforces 455A: Boredom
#include <iostream>
#include <vector>
#include <utility> // pair
#include <algorithm> // max
#define MAX 100001
using namespace std;

long long dp[MAX][2]; // dp[i][0]: i번째 element까지 봤으나 i번째 element를 선택해 제거하지 않았을 경우의 max값
vector<long long> arr; // input
vector< pair<long long, long long> > v; // {element, cnt}

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

	long long N, i, tmp, cnt;
	long long ans = 0;
	cin >> N;

	arr.push_back(-1); // arr[0] = 0
	for (i = 1; i <= N; i++) {
		cin >> tmp;
		arr.push_back(tmp);
	}
	sort(arr.begin(), arr.end());

	// element를 sorting한 다음 sequence 내에서의 개수 구하기
	v.push_back(make_pair(0, 0));
	cnt = 0;
	for (i = 1; i <= N; i++) {
		if (arr[i] != arr[i - 1]) {
			v.push_back(make_pair(arr[i - 1], cnt));
			cnt = 1;
		}
		else cnt++; // arr[i] == arr[i-1]
	}
	v.push_back(make_pair(arr[i - 1], cnt)); // 마지막 element까지 계산해주기

	int size = v.size();
	for (i = 1; i < size; i++) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
		if (v[i - 1].first == v[i].first - 1) {
			dp[i][1] = dp[i - 1][0] + v[i].first * v[i].second;
		}
		else {
			dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + v[i].first * v[i].second;
		}
		ans = max(ans, max(dp[size - 1][0], dp[size - 1][1]));
	}
	cout << ans << endl;
	return 0;
}

새로 배운 내용

전에 다른 문제를 풀 때에도 sequence 내에서 각 element가 몇 개씩 있는지 계산하는 과정이 필요한 적이 있었는데, 그때는 코테 중이라 시간에 쫓겨 푸느라 마지막 원소 처리도 못 해주고 제대로 돌아가지도 않았던 기억이 난다.

교수님은 value와 count 배열을 둘 다 두고 j번째 인덱스로 접근했지만, pair vector로 두면 v.push_back() 때문에 j를 증가시킬 필요도 없고 v[i].first, v[i].second로 접근하면 좋을 것 같아 vector로 관리했다.

Codeforces 327A: Flipping Game

문제

0과 1로 이루어진 sequence가 있을 때 두 인덱스 i, j를 뽑아 그 범위 내의 값들을 한 번 flip한다. 이 때 sequence 내의 1의 개수가 최대가 되도록 하는 문제.

왠지 전에 봤던 것 같은 문제,, 진짜 다 해보면 O(N^3)시간 안에 답을 구할 수 있겠지만, 그러면 시간이 너무 오래 걸린다. DP를 배우는 중이니까 가능한 DP를 사용해 풀어보자.

Idea

DP문제이므로 메모할 배열 dp[i][j]를 선언한다. dp[i][0]은 i번째 원소까지 봤고 i번째 원소가 flip되지 않았을 때, dp[i][1]은 i번째 원소가 flip되었을 때, 1의 개수의 최댓값이다.

i번째 인덱스까지 봤다고 하자. 그러면 i번째 원소의 값을 flip할 때와 그렇지 않을 때, 이렇게 두 가지 경우로 나눌 수 있다.

flip하지 않는 경우는 i-1번째 인덱스까지 봤을 때 가장 좋은 값(max(dp[i-1][0], dp[i-1][1])에다 i번째 원소 값을 더해주면 된다.

flip하는 경우에는 두 가지 케이스가 발생한다.

이미 flip되어 있는 값에 나도 flip 시켜 더해주기
- 이전의 값들이 flip되어있어야 하므로 dp[i-1][1] + (1-a[i])
앞에 값들은 하나도 flip하지 않고 나만 flip하기
- i-1번째까지의 1의 개수에다가 나를 flip한 값을 더해준다.
- ones[]라는 배열을 선언해 ones[i]에 i번째 element까지의 1의 개수를 넣어주었음
- ones[i-1] + (1-a[i])

1과 2중 더 큰 값을 D[i][1]으로 넣어준다.

문제를 풀 때 잊고 있었던 조건 중 하나가 무조건 단 한 번 flip해야 한다는 것이었는데, 이 조건을 고려하지 않아 틀렸다. 예를 들어 입력이 1이거나 1 1 1 1인 경우 flip하지 않는 것이 가장 좋기 때문에 예외처리를 하지 않는 이상 각각 1과 4를 출력했다. 그러나 무조건 flip해야 하므로 실제 정답은 0과 3이어야 한다. 그래서 출력할 때 sequence 내의 모든 element가 1이면, 즉 ones[N] == max(dp[N][0], dp[N][1])이라면 1을 뺀 다음 출력하도록 하니 정답을 구할 수 있었다.

Idea 2

0을 1로, 1을 -1로, 즉 0 1 0 0 1 0 1 0 1 0을 1 -1 1 1 -1 1 - 1 - 1로 바꾸고 합이 제일 큰 구간을 찾으면 된다. 이렇게 풀면 전에 배웠던 max subarray를 쓸 수 있음

Implementation

Input

sequence의 길이 N(1 이상 100이하)와 0/1의 sequence. 문제에서 N의 최댓값이 100이므로 O(N^3)으로 해도 풀리긴 할 듯

Output

부분 flip된 sequence에서 최대로 나올 수 있는 1의 개수

Code

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

int dp[101][2];
int a[101];
int ones[101];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int N, one = 0, i;
	cin >> N;
	for (i = 1; i <= N; i++) {
		cin >> a[i];
		if (a[i] == 1) one++;
		ones[i] = one;
	}
	
	dp[1][0] = a[i];
	dp[1][1] = 1 - a[i];
	
	for (i = 2; i <= N; i++) {
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + a[i];
		dp[i][1] = max(dp[i - 1][1], ones[i - 1]) + (1 - a[i]);
	}

	int tmp = max(dp[N][0], dp[N][1]);
	if (tmp == ones[N]) cout << tmp - 1 << endl; // 무조건 한 번 flip해야 하므로, 다 1로 이루어져 한 번도 flip하지 않는게 나을 때는 강제로 1을 빼줘야 함
	else cout << tmp << endl;
	return 0;
}

Dynamic Programming

Codeforces 189A: Cut Ribbon

Idea

Implementation

Input

Output

Code

Codeforces 455A: Boredom

Idea

Implementation

Input

Output

Code

새로 배운 내용

Codeforces 327A: Flipping Game

Idea

Idea 2

Implementation

Input

Output

Code

Share on: