백준 동아리방 청소!(12019)

동아리방 청소!

1. 힌트

1) 동아리 방을 청소하지 않는다면 최대 $20 \times N$만큼 더러워질 수 있습니다. 범위가 작은 것에 유의합시다.

2) $i$번째 날 저녁에 할 수 있는 선택은 청소를 하거나 안하거나 두가지 뿐입니다. $dp(i, m, k)$ = $i$번째 날 부터 $m$번 골라 청소할 때 현재 더러운 정도가 $k$이면 각 사람들이 느낀 불쾌감의 최소 합으로 정의할 수 있습니다.

3) 최적해를 역추적하는 과정도 비슷한 함수를 정의합니다. 청소를 하는 것과 안하는 것 중에 더 이득인 쪽으로 재귀호출 합니다. 둘다 똑같이 이득인 경우는 오름차순으로 출력해야하므로 청소를 하는 것으로 재귀호출합니다.

2. 접근

1) 입력의 크기

입력의 크기가 작으면 언제나 브루트포스나 혹시 가능하다면 DP를 생각해봅니다. $dp$함수의 인자로 $i$, $m$까지 넣었을 때 cache배열의 크기는 $N\times N$입니다. 여기에 현재 더러운 정도인 $k$를 추가하는데, 최대 더러워질 수 있는 정도가 $20 \times N$이므로 $3$차원 $dp$함수를 정의할 수 있습니다.

2) 선택

$i$번째 날에 할 수 있는 선택은 청소를 하거나(아직 횟수가 남아있다면) 하지 않거나 입니다. $dp$함수 하나의 시간 복잡도는 $O(1)$이므로 총 $O(20\times N^3)$ 의 시간복잡도로 해결할 수 있습니다.

3. 구현

public class Main {
	static int N;
	static int[] S;
	static int[][][] cache;
	
	// i번째 날 부터 m번 골라 청소할 때 현재 더러운 정도가 k이면
	// 각 사람들이 느낀 불쾌감의 최소 합
	static int dp(int i, int m, int k) {
		if (i == N) return 0;
		if (cache[i][m][k] != 0) return cache[i][m][k];
		int min = k * S[i] + dp(i + 1, m, k + S[i]);
		if (m > 0) min = Math.min(min, k * S[i] + dp(i + 1, m - 1, 0));
		return cache[i][m][k] = min;
	}
	
	static void reconstruct(int i, int m, int k, StringBuilder bw) {
		if (i == N) return;
		if (m > 0 && dp(i + 1, m - 1, 0) <= dp(i + 1, m, k + S[i])) {
			bw.append(i + 1).append(" ");
			reconstruct(i + 1, m - 1, 0, bw);
		} else {
			reconstruct(i + 1, m, k + S[i], bw);
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		S = new int[N];
		int M = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
		cache = new int[N][M + 1][N * 20 + 1];
		bw.append(dp(0, M, 0)).append("\n");
		reconstruct(0, M, 0, bw); bw.append("\n");
		System.out.print(bw);
	}

}

1) 시간 복잡도

$O(20\times N^3)$

2) 테스트 케이스

100 4
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 
->380000
->20 40 60 80

모든 $S$의 원소가 똑같다는 가정하에 $M$을 늘리기만 한다면 점점 간격이 촘촘해지네요