[BAEKJOON 백준] 14462 소가 길을 건너간 이유 8 (JAVA)

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

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

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

6
1
2
3
4
5
6
6
5
4
3
2
1

예제 출력 1 복사

5

 

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

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

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와 조건만 다르지 동일한 형태이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int map[][] = new int[2][N + 1];
		for (int i = 0; i < 2; i++) {
			for (int j = 1; j <= N; j++) {
				map[i][j] = Integer.parseInt(br.readLine());
			}
		}
		int dp[][] = new int[N + 1][N + 1];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				if (Math.abs(map[0][i] - map[1][j]) <= 4) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
			}
		}
		System.out.println(dp[N][N]);
	}
}