백준 2352 / LIS(최장 증가 수열), DP / JAVA

오늘은 백준 2352번 '반도체 설계' 문제를 보려고 한다.

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

2352번: 반도체 설계

난이도는 그렇게 어렵지 않았다.(골드 3) 이 문제는 LIS(최장 증가 수열)와 DP로 풀 수 있는 문제이다. 먼저 LIS에 대해서 간단하게 설명을 해 보려고 한다. LIS는 어떤 수열이 주어졌을 때 그 수열의 부분 수열 중에서 가장 길이가 긴 수열을 의미한다. 여러가지 방법으로 이 수열을 구할 수 있겠지만, 가장 일반적인 방법은 dp를 사용하여 순차적으로 탐색을 하면서 dp 배열에 길이를 index로 넣어서 계산하는 O(N^2)의 방법이다. 자세한 방법은 아래 문제 설명을 하면서 소개하려고 한다.

그러면 이제 LIS에 대해서 알았으니 문제를 보도록 하자. 사실 이 문제는 문제를 LIS로 풀어야 한다는 아이디어를 얻기까지가 개인적으로 어려웠던 것 같다.

input으로 왼쪽 포트 오름차순(1번, 2번, 3번, ...)에 대응되는 오른쪽 포트 번호가 주어진다. 문제처럼 4 2 6 3 1 5 이렇게 주어지면, 왼쪽 1번 포트가 오른쪽 4번 포트, 왼쪽 2번 포트가 오른쪽 2번 포트, ... 이렇게 대응이 된다는 의미이다. 그렇게 짝이 주어졌을 때 선이 꼬이지 않고 가장 많은 연결이 가능한 갯수를 구해야 한다.

나는 사실 처음에 그리디로 풀어보려고 했다. 왼쪽 포트, 오른쪽 포트가 담긴 클래스를 하나 만들어서 짝지어진 번호가 낮은 순서대로 우선순위 큐 등을 이용해서 꺼내면서 최대 연결 갯수를 찾는 식으로 말이다. 하지만 그렇게 푸니까 틀렸고 다른 방법을 고민해 보게 되었다.

포트끼리의 연결이 꼬이지 않으려면 어떻게 되어야 할까? A 연결, B 연결이 꼬이지 않으려면 A 왼쪽 포트 < B 왼쪽 포트일 때, A 오른쪽 포트 < B 오른쪽 포트가 모든 포트끼리의 관계에서 성립해야 한다. 아래 그림처럼 말이다. 만약 하나라도 A 왼쪽 포트 < B 왼쪽 포트일 때, A 오른쪽 포트 > B 오른쪽 포트이면 연결은 반드시 꼬이게 된다.

따라서 우리는 주어진 배열(예제에서는 4 2 6 3 1 5)에서 증가하는 수열을 찾으면 된다. 이미 이 수열은 왼쪽 포트가 오름차순으로 index에 매핑되어 있기 때문이다. value값인 오른쪽 배열만 증가하는 수열을 찾으면 꼬이지 않는 포트들끼리 연결을 할 수 있다.

나는 LIS를 구하는 과정에서 DP를 사용하였다. DP 배열을 하나 선언했는데, 이 배열의 index는 증가 수열의 길이이고, value는 그 증가수열에서 가장 큰 값(가장 마지막 값)을 의미한다. 그리고 arr 배열에 대해 loop를 돌기 시작한다.

arr[1] = 4 이고, 증가 수열은 4 하나 이므로 이 값을 dp[1]에 넣어준다.

arr[2] = 2인데, 증가 수열의 길이는 아직까지 1이 최대값이지만, 2는 4보다 작으므로 dp[1] = 2로 업데이트를 해준다. 

3번째 값까지 탐색을 하면 4 6(또는 2 6)이라는 길이가 2인 증가 수열이 나타나게 된다. 따라서 dp[2] = 6으로 값을 업데이트 해 준다.

배열 전체에 대해 loop를 마치면 다음과 같이 dp 배열이 나오게 된다. 이 배열에서 dp[3] = 5 가 가장 높은 인덱스의 값이며, 이는 길이가 3인 증가 수열이 있고, 그 마지막 값이 5라는 의미이다. 따라서 이 문제에서 LIS는 2 3 5가 되며, 문제의 답은 3이 되는 것이다.

내가 제출한 자바 소스코드는 다음과 같다.

아이디어가 재밌고 LIS에 대해서 알고 있다면 어렵지 않게 풀 수 있는 문제였다. 이 문제도 추천한다.