백준 14462 소가 길을 건너간 이유 8 c++ (dp)

문제 출처 : https://www.acmicpc.net/problem/14462

14462번: 소가 길을 건너간 이유 8

문제

존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다.

농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 교통사고를 막기 위해 존은 횡단보도를 설치하려고 한다. 각 횡단보도는 왼쪽과 오른쪽에 있는 목초지를 하나씩 이어야 하고, 길에 수직일 필요는 없다. 물론 사이가 좋은 소들끼리 연결해야 한다. 각 목초지에는 최대 한 개의 횡단보도만 있어야 한다. 그리고 횡단보도가 겹치면 안 된다.

그의 농장을 둘러보면서 가능한 한 많이 횡단보도를 설치해주자.

입력

첫 줄에 N이 주어진다. 다음 N줄에는 길의 왼쪽에 있는 목초지별로 소의 종 번호가 차례대로 주어진다. 각 종은 한 번씩 나타난다. 그 다음 N줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.

출력

조건을 만족하도록 설치할 수 있는 횡단보도의 최대 개수를 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

2021.04.22 - [알고리즘 문제 풀이/백준] - 백준 2565 전깃줄 c++

문제를 읽고 전깃줄 문제가 생각났지만, 양쪽 목초지의 소 위치들이 고정되어있기 때문에 같은 방식으로는 풀 수 없다.

이후 그리디하게 짜는 법을 더 생각해봤지만, 정렬도 불가하기에 답이 보이지 않았고

dp로 푸는 게 정해라는 결론이 나왔다.

우선 왼쪽 목초지의 인덱스를 i,

오른쪽 목초지의 인덱스를 j라 할 때,

1. i와 j를 연결하고 i+1, j+1로 넘어가기

2. i를 버리고 i+1, j로 넘어가기

3. j를 버리고 i, j+1로 넘어가기

3가지 길이 있다.

dp[i][j]를 현재 i와 j를 검사할 때의 횡단보도 최대 개수라고 할 때,

dp[i][j]는 dp[i-1][j] 과 dp[i][j-1]의 값 중 큰 값을 가져오고,

abs(arr[i] - arr[j])  <=4 라면, dp[i-1][j-1]에 1을 더해준다.

이 점화식... 낯설지 않다.

맞다.

LCS와 조건만 다르지 동일한 형태이다.

문자열에만 사용할 줄 알았던 LCS 알고리즘 형태를 이런 문제에서도 적용할 수 있다니

굉장히 재밌는 문제이다.

비슷한 유형들을 더 풀어본다면, 굉장한 경쟁력이 될 거 같다.

비슷한 문제 : https://www.acmicpc.net/problem/9177

코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
//1<=n<=1000
int n;
int arr1[1001],arr2[1001];
int dp[1001][1001];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr1[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> arr2[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			if (abs(arr1[i] - arr2[j]) <= 4) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
		}
	}
	cout << dp[n][n];
	return 0;
}