문제 링크
문제
티어: 골드 1
알고리즘: dp
남규는 동아리 방 관리자이다. 요즘 동아리 방 사용자가 많아지고 동아리 방이 더러워져서 사람들이 불쾌함을 느끼고 있다.
한 사람이 느끼는 불쾌함은 동아리 방의 더러움과 같다. 즉, 동아리 방의 더러움이 3이고 그날 5명이 동아리방에 온다면 5명 모두 불쾌함을 3을 느끼게 되어 그 날 각 사람들이 느낀 불쾌함의 총합은 15가 된다. 그리고 동아리방의 더러움은 사람이 a명 들어오고 나가면 a만큼 증가한다. 그래서 사람들의 불쾌함을 최소로 하기 위해 동아리 방을 청소해야한다.
하지만 남규는 게을러서 총 N일중에 M번만 청소를 하려고 한다. 남규는 최대한 전체 사람들의 불쾌함의 총합이 적도록 청소 계획을 짜려한다.
N일 동안의 들어오는 사람을 미리 알 수 있다고 할 때, 어떻게 청소 하는 것이 불쾌함이 적어질지 남규는 몹시 궁금하다. 처음 시작의 동아리방의 더러움은 0이다.
입력
첫째 줄에는 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ min(10, N))이 주어진다. 그리고 두 번째 줄에는 그 날 출입하는 사람의 수 Pi (1 ≤ Pi ≤ 20)가 N개 주어진다.
출력
첫째 줄에는 N일 까지의 각 사람들이 느낀 불쾌함의 총합의 최솟값을 출력하고 두 번째 줄에는 그 때 청소한 날짜를 오름차순으로 출력한다. 정답이 여러 가지인 경우에는 사전 순으로 앞서는 것을 출력한다. 단, 청소는 항상 그 날 학생들이 다 나가고 난 후 저녁에 한다고 한다.
풀이
N일 까지 M번 청소했을 때 불쾌함의 총합의 최솟값을 출력하고, 청소한 날짜를 오름차순으로 출력해야 한다. (가능한 경우가 여러 개라면 사전 순으로 앞서는 것을 출력한다.)
최솟값을 구하기 위해서는 일마다 청소를 하는 경우와 청소를 하지 않는 경우를 따져봐야 한다.
그냥 브루트 포스식으로 풀면 2^100이 되기 때문에 중복 경우를 따져봐야 한다.
만약 현재 아침을 기준으로 더러움 정도(a)와 남은 청소 횟수(m)와 현재 일(n)이 같다면 이 경우는 두 번 탐색할 필요 없이 딱 한 번만 탐색하면 된다.
그래서 dp는 dp[N][M][Nx20]으로 정의할 수 있다. N x 20는 a의 최댓값이다.
예를 들어 dp[3][1][11]이면 3일 째 아침이며, 남은 청수 횟수는 1이고, 더러움 정도는 11일 때의 최적값이다.
그래서 특정 상태(dp[3][1][11])에서 다음 탐색의 경우는 다음 두 가지로 나뉜다.
- 청소를 하는 경우 -> dp[4][0][0]
- 청소를 하지 않은 경우 -> dp[3][1][nextA]
이 두 값을 비교해서 더 작은 값을 넣어줘야 최적 값을 구할 수 있다.
다음은 청소한 날짜를 구해줘야 한다. 각 dp에는 최적 값을 만드는 다음 dp를 연결한다면, 최적 값의 청소한 날짜를 간단하게 구해줄 수 있다.
중요한 점은 가능한 경우가 여러 개라면 사전 순으로 앞서는 것을 출력해야 하기 때문에
특정 상태(dp[3][1][11])에서 두 경우의 값이 같다면, 청소를 한 경우를 넣어줘야 한다.
왜냐하면 현재 n이 3이고, m이 1인 상태에서 m을 3에서 사용하는 것이 그 이후 4 ~ ..에서 사용하는 것보다 사전 순으로 앞서기 때문이다.
이 풀이의 시간 복잡도는 O(N^2 x M)이 된다.
소스 코드
import java.io.*;
import java.util.*;
class DpDetail {
int v, cn;
DpDetail next;
DpDetail(int v, int cn, DpDetail next) {
this.v = v;
this.cn = cn;
this.next = next;
}
}
public class Main {
static int N, M, maxA;
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());
M = Integer.parseInt(st.nextToken());
maxA = N * 20;
int[] arr = new int[N + 1];
StringTokenizer st2 = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
arr[i] = Integer.parseInt(st2.nextToken());
}
DpDetail[][][] dp = new DpDetail[N + 1][M + 1][maxA + 1]; //아침 상태를 기준으로함
DpDetail answer = findAnswer(1, M, 0, arr, dp);
StringBuilder sb = new StringBuilder();
sb.append(answer.v).append("\n");
DpDetail cur = answer;
while(cur != null) {
if(cur.cn != -1) {
sb.append(cur.cn).append(" ");
}
cur = cur.next;
}
System.out.println(sb.toString().trim());
}
static DpDetail findAnswer(int n, int m, int a, int[] arr, DpDetail[][][] dp) {
if(n == (N + 1)) {
return new DpDetail(0, -1, null);
}
if(dp[n][m][a] != null) {
return dp[n][m][a];
}
DpDetail clienNext = null;
if(m > 0) {
//청소 가능
clienNext = findAnswer(n + 1, m - 1, 0, arr, dp); //청소 후 다음날 아침 상태
}
DpDetail noClienNext = findAnswer(n + 1, m, a + arr[n], arr, dp); //청소 x 다음날 아침 상태
int nv = a * arr[n];
if((clienNext != null) && (clienNext.v <= noClienNext.v)) {
dp[n][m][a] = new DpDetail(nv + clienNext.v, n, clienNext);
} else {
dp[n][m][a] = new DpDetail(nv + noClienNext.v, -1, noClienNext);
}
return dp[n][m][a];
}
}