[백준 번호]https://www.acmicpc.net/problem/번호
문제 조건
존 (우리가 지금까지 도와 주었던 존과는 다른 인물이다)의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종 (1 ≤ N ≤ 1000)이다. 만약 |a−b| ≤ 4라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다.
농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 교통사고를 막기 위해 존은 횡단보도를 설치하려고 한다. 각 횡단보도는 왼쪽과 오른쪽에 있는 목초지를 하나씩 이어야 하고, 길에 수직일 필요는 없다. 물론 사이가 좋은 소들끼리 연결해야 한다. 각 목초지에는 최대 한 개의 횡단보도만 있어야 한다. 그리고 횡단보도가 겹치면 안 된다.
그의 농장을 둘러보면서 가능한 한 많이 횡단보도를 설치해주자.
문제 입력
첫 줄에 N이 주어진다. 다음 N줄에는 길의 왼쪽에 있는 목초지별로 소의 종 번호가 차례대로 주어진다. 각 종은 한 번씩 나타난다. 그 다음 N줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.
문제 풀기 전 설계
문제를 보면 2차원 dp 배열을 사용해 왼쪽 농장 인덱스 i와 오른쪽 농장 인덱스 j의 값을 비교해서
- abs(left[i] - right[j])가 4 이하인 경우
dp[i][j] = dp[i - 1][j - 1] + 1 - 그렇지 않은 경우
dp[i][j] = dp[i - 1][j]와 dp[i][j - 1] 중 큰 값
라는 점화식이 나온다. 이는 LCS의 점화식과 매우 유사하다.
문제 코드
package Baekjoon.dp;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ_14462 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] left = new int[n + 1];
int[] right = new int[n + 1];
for (int i = 1; i <= n; i++) left[i] = Integer.parseInt(br.readLine());
for (int i = 1; i <= n; i++) right[i] = 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++) {
if (Math.abs(left[i] - right[j]) <= 4) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
System.out.println(dp[n][n]);
}
}
문제 풀이
왼쪽 농장의 인덱스 i, 오른쪽 농장의 인덱스 j라고 하면 i와 j의 관계에서 나올 수 있는 경우는 세 가지이다.
1. i와 j를 연결 (left[i]와 right[j]의 차이가 4 이하인 경우)
2. 연결하지 않고 i + 1, j로 건너뛰는 경우
3. 연결하지 않고 i, j + 1로 건너뛰는 경우
결국 전체 풀이는 LCS와 같다.
Review
문자열에서만 사용할 것 같았던 LCS가 다르게 사용되는 것이 재밌었다.
