문제 출저
https://www.acmicpc.net/problem/29792
문제 풀이
n개의 캐릭터 중 m개를 선택하여 보스를 잡아서 메소의 최대값을 구해야 합니다.
n개의 케릭터는 각각 데미지가 있습니다. m개를 선택할 때 대미지가 큰 순서대로 선택했습니다. PriorityQueue 사용
보스는 체력과 메소가 주어집니다.
한 케릭터당 사냥 시간은 15분 입니다. 대미지는 1초당 대미지 입니다. 즉 900초의 시간이 주어집니다.
900초 길이를 가진 1차원 int 배열을 만들어 배낭 알고리즘으로 최댓값을 구하고 더합니다.
이 떄 입력값의 범위가 크므로 long을 사용합니다.
배낭 알고리즘은 현재 보스를 선택했을 때랑 선택하지 않을 때를 비교하여 더 큰 값을 dp인 1차원 배열에 저장하여 최대값을 구하는 기법입니다.
소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/*
규칙적인 보스돌이
https://www.acmicpc.net/problem/29792
하루에 한 케릭터들은 최대 15분씩 사냥 가능
900초
95% 오류
모든 계산을 한 다음 변환을 해야했다.
보스 잡을 시간을 구할 때 나누고 int로 변환하고 나머지가 있을 경우 +1을 하니 틀렸다.
나누고 나머지가 있을 경우 +1을 하고 int로 변환하니 통과했다.
*/
public class Main {
static int n; // 보유한 케릭터 개수
static int m; // 하루에 사용할 케릭터
static int k; // 보스의 가짓수
static PriorityQueue<Long> d;
static long[] hp;
static long[] meso;
static long answer;
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());
k = Integer.parseInt(st.nextToken());
d = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
d.add(Long.parseLong(br.readLine()));
}
hp = new long[k];
meso = new long[k];
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
hp[i] = Long.parseLong(st.nextToken());
meso[i] = Long.parseLong(st.nextToken());
}
while(m-->0) {
long damage = d.poll();
solution(damage);
}
System.out.println(answer);
}
public static void solution(long damage) {
long[] dp = new long[901];
for (int i = 0; i < k; i++) {
long time = hp[i] / damage;
if (hp[i] % damage != 0) time += 1;
if(time > 900) continue;
for (int j = 900; j >= 0; j--) {
if (j-time >= 0) dp[j] = Math.max(dp[j], dp[j- (int) time] + meso[i]);
}
}
answer += dp[900];
}
}