방과후
ALGORITHM NOTE약 1분

BOJ 26093 - 고양이 목에 리본 달기

그냥 다 다른거 달아주면 되잖아

#algorithm#boj#gold#dp
아카이브로 돌아가기

문제 링크

문제

외로운 윤제는 고양이를 키우기로 했다.

N마리의 고양이를 입양하기로 한 윤제는 고양이들에게 리본을 달아주기 위해 K종류의 리본을 충분히 준비했다. 즉, 각 리본의 개수는 무한하다. 각 고양이마다 리본의 종류에 따라 좋아하는 정도가 다르고, 이를 만족도로 나타낼 수 있다.

고양이들을 번호순으로 한 줄로 세우고 리본을 달아주려고 하는데, 각 고양이는 자신과 이웃한(왼쪽 혹은 오른쪽) 고양이와 같은 종류의 리본을 다는 것을 굉장히 싫어한다. 윤제는 고양이들이 싫어하는 상황을 피하면서 각 고양이의 리본에 대한 만족도의 총합을 극대화하고 싶다.

이 조건을 만족하는 만족도 합의 최댓값을 윤제에게 알려주자.

입력

첫 번째 줄에는 고양이의 수 N과 리본 종류의 수 K가 공백으로 구분되어 주어진다. (1 <= N <= 100, 2 <= K <= 10000)

다음 N개의 줄에는 각각 K개의 정수 aᵢ,₁, ..., aᵢ,ₖ가 공백으로 구분되어 주어진다. aᵢ,ⱼ는 i번 고양이가 j번 리본을 달았을 때의 만족도를 의미하며, 1 <= aᵢ,ⱼ <= 10000을 만족한다.

출력

고양이들이 싫어하는 상황을 피하면서 리본을 달아줄 때, 각 고양이의 만족도의 총합의 최댓값을 출력한다.

풀이

기본 DP는 dp[i][j] = i번째 고양이까지 봤을 때, i번째가 j번 리본을 달았을 때의 최대 만족도로 잡을 수 있다. 점화식은 dp[i][j] = value[i][j] + max(dp[i-1][x])인데, 단 x != j여야 한다.

문제는 이 식을 그대로 계산하면 이전 행의 모든 색을 매번 훑어야 해서 O(NK2)O(NK^2)가 된다는 점이다. K가 최대 10000이기 때문에 이 방식은 너무 느리다.

코드에서는 이전 행에서 가장 큰 값과 두 번째로 큰 값을 미리 구한다. 그러면 현재 색 j가 이전 행의 최고값을 만든 색과 다르면 그 최고값을 그대로 쓰면 되고, 같으면 두 번째 값을 쓰면 된다.

이렇게 하면 각 행마다 최고값 두 개만 관리해도 모든 색을 O(K)O(K)에 갱신할 수 있어서 전체가 O(NK)O(NK)로 줄어든다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
	
	static int[][] graph;
	static int N, K;
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		graph = new int[N][K];
 
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < K; j++) 
				graph[i][j] = Integer.parseInt(st.nextToken());
		}
		
		int ans = solve();
		System.out.println(ans);
	}
	
	static int solve() {
		int[][] dp = new int[N][K];
		
		// 첫 번째 고양이
		for (int j = 0; j < K; j++) 
			dp[0][j] = graph[0][j];
		
		// 두 번째 고양이 부터..
		for (int i = 1; i < N; i++) {
			int first = 0;
			int firstIdx = 0;
			int second = 0;
			
			// 1등, 2등 구하기
			for (int j = 0; j < K; j++) {
				int value = dp[i - 1][j];
				
				if (value > first) {
					second = first;
					first = value;
					firstIdx = j;
				} else if (value > second) {
					second = value;
				}
			}
			
			// 1등 인덱스와 같다면 2등의 값으로, 아니라면 1등 값으로
			// 2등 인덱스는 연산 시 필요하지 않음
			for (int j = 0; j < K; j++) {
				if (firstIdx == j) 	dp[i][j] = graph[i][j] + second;
				else	dp[i][j] = graph[i][j] + first;
			}
		}
		
		int ans = Integer.MIN_VALUE;
		for (int j = 0; j < K; j++) 
			ans = Math.max(ans, dp[N - 1][j]);
		return ans;
	}
 
}

복잡도

  • 시간 복잡도: O(NK)O(NK)
  • 공간 복잡도: O(NK)O(NK)

마무리

핵심은 인접 색이 달라야 한다는 조건을 정직하게 보되, 이전 행의 최고값 두 개만 들고 가는 것이다. K가 큰 문제에서는 이런 최댓값 최적화가 정말 중요하다.