2020/07/07 공부 - dynamic programming

어제에 이어서 DP 공부를 했다. 작년 이맘쯤에 객체지향 프로그래밍 첫 과제로 BFS와 LIS가 나왔었는데, 당시 BFS는 이해했는데 LIS는 이해를 잘 못했었다. 그 해 여름방학 관심 생겨서 공부했을 때도 다른 DP는 점화식으로 어떻게 풀었는데 LIS와 냅색은 잘 이해하지 못했었던 기억이 있다.

 각설하고, 오늘은 문제를 몇 개 풀었다.

 먼저 1463번. 1로 만드는 데 몇 번의 연산이 필요하냐는 문제이다. DP의 정석으로, 필요한 것은 미리 계산해 두고, 점화식에서 이 미리 계산해둔 것들을 불러오는 방식을 취한다.

 

void solve() {
	int N;
	cin >> N;
	vector<int> make_one(N+1);
	make_one[0] = 0;
	make_one[1] = 0;
	if (N >= 2)make_one[2] = 1;
	if (N >= 3)make_one[3] = 1;
	
	
	for (int i = 4; i <= N; i++) {
		int candidate1 = 1000000000;
		int candidate2 = 1000000000;
		int candidate3 = 1000000000;
		if (i % 3 == 0) {
			candidate1 = make_one[i / 3] + 1;
		}
		if (i % 2 == 0) {
			candidate2 = make_one[i / 2] + 1;
		}
		candidate3 = make_one[i - 1] + 1;
		make_one[i] = min(candidate1, min(candidate2, candidate3));
	}
	cout << make_one[N];
}

 

 다음, 10844번. n자리 숫자에서 계단수는 몇개 있는가? 1자리 숫자는 1, 2, 3, ... , 8, 9로 총 9개 있다. 2자리 숫자는 1에서 10, 12가, 2에서 21, 23이, ... , 8에서 87, 89가, 9에서 98이 분화해 나간다. 예전에 풀었을 때는 2시간동안 힘겹게 풀었는데 요새 다시 보니 쉬운 것 같다.

 아무튼, 끝자리가 0이면 무조건 다음 숫자는 1밖에 올 수 없다. 유사하게 끝자리가 9면 다음 숫자는 8밖에 없다. 끝자리가 1부터 8이라면 다음 숫자는 2개가 올 수 있다. 이 점에 착안해서 끝 자리의 배열 10개를 만들고, 끝자리가 n인 계단수가 몇개인지 세는 방식을 도입했다.

 

void solve() {
	int N;
	cin >> N;
	vector<int> stair_number(10);
	for (int i = 0; i < 10; i++) {
		stair_number[i] = 1;
	}
	stair_number[0] = 0;


	for (int i = 0; i < N-1; i++) {
		int temp[10] = {};
		temp[0] = stair_number[1];
		for (int j = 1; j <= 8; j++) {
			temp[j] = (stair_number[j - 1]%CONDITION + stair_number[j + 1]%CONDITION)%CONDITION;
		}
		temp[9] = stair_number[8];

		for (int j = 0; j < 10; j++) {
			stair_number[j] = temp[j]%CONDITION;
		}
	}
	int answer = 0;
	for (int i = 0; i < 10; i++) {
		answer = (answer % CONDITION + stair_number[i] % CONDITION) % CONDITION;
	}
	cout << answer;
}
​

 

 올리는 지금 생각해 보면, 1부터 8까지는 그냥 하나로 묶어서 해도 되었지 않았을까? 하는 생각이 든다.

다음, 2156번.

 어제? 푼 계단 오르는 것과 굉장히 유사하다. 차이점이라면 i번째에서 만드시 i번째 잔의 수를 취할 필요가 없단느 것, 그래서 max 함수에 1개만 추가하면 된다. 계단 오르는 문제와 동일하게 DP[i]가 의미하는 것은 i번째 잔까지 계산했을 때 최대 점수이고, 3개 연속 마실 수 없기 때문에 총 3개의 경우의 수가 존재한다.
 1) i-2번째 잔의 최대 점수에서, i-1번째 잔을 건너뛴 후 i번째 잔을 마시는 경우
 2) i-3번째 잔의 최대 점수에서, i-2번째 잔을 건너뛴 후 i-1번째, i번째 잔을 마시는 경우
 3) i-1번째 잔까지 최대 점수 + i번째 잔을 마시지 않는 경우
이렇게하면 모든 경우의 수에서 3개 연속되는 잔을 마시지 않는다는 것이 보장된다.

 

int dynamic_programming(vector<int>& wine, int N) {
	vector<int> DP(N, 0);

	// 3개 연속 불가

	DP[0] = wine[0];
	if(N >= 2) DP[1] = wine[0] + wine[1];

	for (int i = 2; i < N; i++) {
		DP[i] = max(DP[i - 2] + wine[i], max(DP[i - 3] + wine[i - 1] + wine[i], DP[i-1]));
	}
	return DP[N - 1];
}

 

입/출력하면 끝.

 

void solve() {
	int N;
	cin >> N;
	vector<int> wine(N);
	for (int i = 0; i < N; i++) {
		cin >> wine[i];
	}
	cout << dynamic_programming(wine, N);
}

 

 

 다음, 1912번 연속합이다.

 이 문제는 조금 생각을 했는데, 예전에 푼 부분합?인가 유사한 문제랑 헷갈려서 처음부터 다 더한 다음에, 최대 값 - 최소값 하면 되지 않나? 라고 함정에 빠졌다. 이 알고리즘이 뭐였는지 기억나지 않는데... 음 나중에 공부하다보면 떠오를거다.

 아무튼, DP문제인 만큼 점화식을 세운다. DP[i]가 i번째까지 수를 보았을 때 최대 부분합이라고 하자. 그러면 DP[i]는 이전 DP[i-1] + input[i], 즉 계속 부분합 수열을 이어갈 건지, 아니면 input[i]로 부분합 수열을 끊고 새로 시작할 건지 2개중에만 택해주면 항상 더 커지는 방향으로만 부분합이 만들어지기 때문에 이렇게 만들면 된다.

 

int dynamic_programming(vector<int>& input, int N) {
	vector<int> DP(N, 0);
	DP[0] = input[0];
	for (int i = 1; i < N; i++) {
		DP[i] = max(input[i], DP[i - 1] + input[i]);
	}
	int temp = -1000000000;
	for (int i = 0; i < N; i++) {
		if (temp < DP[i]) temp = DP[i];
	}
	return temp;
}

 

입/출력하면 끝.

 

void solve() {
	int N;
	cin >> N;

	vector<int> input(N);
	for (int i = 0; i < N; i++) {
		cin >> input[i];
	}
	cout<<dynamic_programming(input, N);
}

 

 마지막으로 12865번 냅색 문제이다. 뭐 0/1 냅색이니 greedy니 많은 설명이 있지만 다른 블로그 참고하면서 공부했으니까 좀 더 자세한 내용을 원하면 다른 블로그를 참고하는 걸 추천한다. 필자는 https://gsmesie692.tistory.com/113 여기를 참고했다.

 예전에 이해하지 못했던 점화식을 이해해서 기분이 좋다. 경험이 많아지니 이해하는 속도가 점점 빨라지는 것 같긴 하다.

 처음에는 '가성비 높은거만 담으면 되지 않나?'라고 생각했는데, 그렇게 하면 허용되는 무게가 7일 때 (weight, value)가 (5, 12)인 것을 (4, 8), (3, 6)인 것보다 우선하게 담게 되어서 전자는 value가 12인 반면 후자는 14로 좀 더 큰 값이 나온다. 그래서 얌전하게 그냥 DP로 풀었다.

 이문제는 O(NK)만큼 걸린다. DP를 2차원 vector로 설정하기 때문인데, DP[i][j]가 의미하는 것은 i번째 물건까지 봤을 때 허용되는 무게가 j일 때 vlaue의 최댓값이다. 그래서 점화식은 무게가 j일 때 i번째 물건을 담을 수 있는 경우와 그렇지 않은 경우로 나누어야 한다.

 DP[i][j]에서 j가 weight[i]보다 크다면 해당 물건을 담을 수 있다는 것이다. 그러면 value는 DP[i-1][j-weight[i]] + value[i]가 될 것이다. 각 물건을 1개밖에 못 담으니까 i-1번째 row에 접근하고, weight에 대해서는 j로 접근해 버리면 j-1에서 어떤 물건을 담았을 경우에는 이상해질 수 있기 때문이다.

 반면, i번째 물건을 take하지 않으면 DP[i-1][j]가 될 것이다.

 그래서 점화식이 아래과 같이, 물건을 담을 수 있는 경우에만  max(DP[i-1][j], DP[i-1][j-weight[i]] + value[i]), 아닌 경우는 바로 DP[i-1][j]가 된다.

 

void solve() {
	int N, K;
	cin >> N >> K;
	vector<int> weight(N+1);
	vector<int> value(N+1);
	for (int i = 1; i < N+1; i++) {
		cin >> weight[i];
		cin >> value[i];
	}
	weight[0] = 0; value[0] = 0;
	vector<vector<int>> DP(N+1, vector<int>(K+1));
	for (int i = 0; i <= N; i++) DP[i][0] = 0;
	for (int j = 0; j <= K; j++) DP[0][j] = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K; j++) {
			if (j - weight[i]>=0) {
				DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - weight[i]] + value[i]);
			}
			else {
				DP[i][j] = DP[i - 1][j];
			}
		}
	}
	cout << DP[N][K];
}