https://www.acmicpc.net/problem/19645
19645번: 햄최몇?
세 모질이들 관우, 철환, 길원이가 모였다. 모질이들은 모이면 서로 '햄버거 최대 몇 개 드실 수 있나요?'의 준말인 '햄최몇?'을 시전하며 자랑을 하기 바쁘다. 막내 길원이는 문득 중요한 사실을
www.acmicpc.net
문제
세 모질이들 관우, 철환, 길원이가 모였다. 모질이들은 모이면 서로 '햄버거 최대 몇 개 드실 수 있나요?'의 준말인 '햄최몇?'을 시전하며 자랑을 하기 바쁘다.
막내 길원이는 문득 중요한 사실을 깨달았다. 바로, 개수가 중요한 것이 아니라 최대 효용이 중요하다는 것이었다! 이들은 바로 N개의 햄버거를 준비했다. 그리고 이 햄버거를 사이좋게 나누어 먹었다. 각 모질이들이 얻을 수 있는 효용은 이들이 먹은 햄버거들의 효용의 합이다. 또한 나름의 서열과 규칙이 있어, 존경하는 선배님들보다는 높은 효용을 누려서는 안 된다.
막내 길원이는 선배님들을 존경하기 때문에 규칙을 따라야 하는 한편, 햄버거를 잘 분배하여 본인이 얻을 수 있는 효용이 최대가 되도록 하고 싶다.
입력
첫 번째 줄에 N (1 ≤ N ≤ 50)이 주어진다. N은 햄버거의 수이다.
두 번째 줄에 N개의 양의 정수 ai (1 ≤ ai ≤ 50)가 공백으로 구분되어 주어진다. 각각의 값은 햄버거의 효용을 의미한다.
출력
세 모질이 중 막내 길원이가 얻을 수 있는 효용의 합의 최댓값을 출력한다.
막내가 선배들보다 작은 효용 중에 최댓값을 가져야 한다.
선배는 철환, 길원으로 2명이 있다.
막내 효용은 전체 효용에서 두 명의 효용을 뺀 값이 될 것이다.
이 값 중에 최댓값을 구하면 된다.
int last = sum - i - j; //i, j는 두 명의 선배의 효용
그럼 이제 두 명의 효용에 대해서만 구하면 된다.
효용이 가능한 지 여부를 확인한다.
i번째의 햄버거에 대해서 선택한 경우, 아닌 경우를 따진다.
문제에서 길원이가 선배들보다 작기만 하면 되므로, 다른 선배들끼리는 크고 작음을 따지지 않아도 된다.
즉, x가 y보다 크지않아도 된다.
그리고 두 선배 x, y의 효용의 합이 전체 효용인 sum보다는 작아야하므로 조건도 걸어주었다.
boolean[][] dp = new boolean[sum + 1][sum + 1];
dp[0][0] = true;
for (int i = 1; i <= N; i++) {
for (int x = sum; x >= 0; x--) {
for (int y = sum - x; y >= 0; y--) {
if (x - a[i] >= 0)
dp[x][y] |= dp[x - a[i]][y];
if (y - a[i] >= 0)
dp[x][y] |= dp[x][y - a[i]];
}
}
}
[5, 10, 15] 일 경우,
첫 번째의 햄버거는 효용이 5이므로,
- dp[5][0]와 dp[0][5]가 true이다.
dp[0][0] = true 이므로, dp[5][0] |= dp[5-5][0]; 은 true이다.
두 번째의 햄버거는 효용이 10이므로,
- dp[10][0], dp[0][10]는 두 번째 햄버거만 선택한 경우
- dp[15][0], dp[0][15]는 첫 번째와 두 번째 햄버거를 선택한 경우
- dp[10][5], dp[5][10]도 가능
dp[10][5] |= dp[10-10][5]; 로 첫 번째에서 dp[0][5] = true; 를 구했으므로 가능하다.
세 번째의 햄버거는 효용이 15이므로,
- dp[15][0], dp[0][15]는 세 번째 햄버거만 선택한 경우
- dp[20][0], dp[0][20], dp[15][5], dp[5][15]는 첫 번째와 세 번째 햄버거를 선택한 경우
- dp[25][0], dp[0][25], dp[20][5], dp[5][20], dp[15][10], dp[10][15]는 두 번째와 세 번째 햄버거를 선택한 경우
- dp[30][0], dp[0][30], dp[25][5], dp[5][25], dp[20][10], dp[10][20], dp[15][15]는 모든 햄버거를 선택한 경우
이렇게 하면
효용이 가능한 dp는 true가 되어있을 것이다.
그 중에서 선배보다 작으면서 최댓값을 구한다.
int answer = 0;
for(int i=0; i<=sum; i++){
for(int j=0; j<=i; j++){
int last = sum - i - j;
if(dp[i][j] && (j >= last)){ //효용 조건에 만족 && 선배보다 작은 값
answer = Math.max(answer, last); //중에 최대값
}
}
}
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] a = new int[N + 1];
int sum = 0;
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
a[i] = Integer.parseInt(st.nextToken());
sum += a[i];
}
boolean[][] dp = new boolean[sum + 1][sum + 1];
dp[0][0] = true;
for (int i = 1; i <= N; i++) {
for (int x = sum; x >= 0; x--) {
for (int y = sum - x; y >= 0; y--) {
if (x - a[i] >= 0)
dp[x][y] |= dp[x - a[i]][y];
if (y - a[i] >= 0)
dp[x][y] |= dp[x][y - a[i]];
}
}
}
int answer = 0;
for (int i = 0; i <= sum; i++) {
for (int j = 0; j <= i; j++) {
int last = sum - i - j;
if (dp[i][j] && (j >= last)) {
answer = Math.max(answer, last);
}
}
}
System.out.println(answer);
}
}