Coding Test - Dynamic Programming

Dynamic Programming

0. intro

• DP 문제는 뭔가 작은 값들을 계산하다 보면 결국 큰 값도 결과가 나올 수 있을 것 같은 문제에서 쓰기
• 시간 복잡도 줄이기
• prefix sum 기법도 있다. (BOJ 11659)

1. DP 문제를 위한 흐름

1) 테이블 정의하기
2) 점화식 찾기
3) 초기값 찾기

2. DP를 풀 때 팁

(정답은 아니고 풀다가 생각을 정리한 것 들입니다.)

• 점화식을 만들 때 d[1] 부터 계산해 나가면서 규칙 찾아내는 식으로 풀기
• 단순히 1차원 배열로 해결이 안될 것 같으면 2차원 배열도 생각해보기
• 점화식이 잘 안 만들어 지면 맨 끝값부터 처리하는 것도 생각해보자 (BOJ 15486)
• 점화식 만들 때는 현재 시점에 어떠한 행동을 했다고 가정했을 때, 과거의 값들에 대한 비교를 통해 현재 점화식 값을 설정한다.
• 초기값은 for문을 돌리면서 초기값으로 필요할 것들을 직접 대입해서 설정해주기

3. DP 문제 예시

예시1) BOJ 2579 계단 오르기

#include <iostream>
using namespace std;

int n;
int board[305];
int d[305][305];

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

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

	d[1][1] = board[1];
	d[1][2] = 0;
	d[2][1] = board[2];
	d[2][2] = board[1] + board[2];

	for (int i = 3; i <= n; ++i)
	{
		d[i][1] = max(d[i - 2][2], d[i - 2][1]) + board[i];
		d[i][2] = d[i - 1][1] + board[i];
	}
	cout << max(d[n][1], d[n][2]);
}

• 점화식 부분)
• d[i][j] : i번째 계단을 밟은것 / j번 연속 밟은 것
• d[i][1]
  • 현재 i 번째 계단을 밟았다고 (현재시점) 했을 때 j는 1이므로 한번 연속 밟았으니, 하나 전 계단은 밟을 수 없음 (하나 전 계단도 밟았으면 j가 2여야 하므로)
  • 두개 전 계단을 밟았을 때 (과거시점) 연속 1번 밟은 것과 연속 2번 밟은 것 중 큰 값을 가져오고
  • 마지막으로 현재의 계단을 밟았을 때 값을 더해준다.
• d[i][2]
  • 현재 i 번째 계단을 밟았다고 (현재시점) 했을 때, 연속 두번 밟았으므로
  • 하나 전 계단 (과거시점) 은 무조건 밟아야한다.
  • 마지막으로 현재 계단에 대한 값도 더해주면 된다.

예시2) BOJ 9465 스티커

#include<iostream>
using namespace std;

int t, n;
int board[2][100005];
int d[100005][3]; //(값, 마지막으로 선택한 타일)

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
		
	cin >> t;

	while (t--)
	{
		cin >> n;

		for (int i = 0; i < 2; ++i)
			fill(board[i], board[i] + n, 0);

		for (int i = 0; i < n; ++i)
			fill(d[i], d[i] + 3, 0);

		for (int i = 0; i < 2; ++i)
		{
			for (int j = 0; j < n; ++j)
				cin >> board[i][j]; // board[0][1] 은 첫줄 2번째
		}
		
		d[0][0] = 0;
		d[0][1] = board[0][0];
		d[0][2] = board[1][0];	

		if (n == 1)
			cout << max(max(d[0][0], d[0][1]), d[0][2]) << "\n";
		else
		{
			for (int i = 1; i < n; ++i)
			{
				//첫줄 붙이거나 둘째줄 붙이거나 안붙이거나
				d[i][0] = max(max(d[i - 1][1], d[i - 1][2]), d[i - 1][0]);
				d[i][1] = max(d[i - 1][0], d[i - 1][2]) + board[0][i]; //첫줄 붙임
				d[i][2] = max(d[i - 1][0], d[i - 1][1]) + board[1][i]; //둘째줄 붙임
			}
			
			cout << max(max(d[n - 1][0], d[n - 1][1]), d[n - 1][2]) << "\n";
		}
	}
}