백준 14501 풀이
퇴사 2
https://www.acmicpc.net/problem/14501
풀이
처음에는 백트래킹을 통해 얻을 수 있는 페이를 모두 계산해 최대를 구하려고 했다. 하지만 코드가 의도대로 동작하지 않았고 디버깅에 어려움이 있어 다른 방법을 생각하고 있었다.
문제의 분류에 dp가 있어서 dp로 풀어보기로 했다.
하지만 그래도 쉽지 않았고 다른 사람의 점화식을 참고했다.(dp 너무 어렵다... ㅠㅠ)
현재 일(i)에서 상담일(t)을 더해 범위(n)를 초과하지 않는 경우 금액(p)을 더해준다.
if (i + t <= n) dp[i] = max(dp[i + t], dp[i + t] + p)
하지만 위 점화식을 사용을 하면 아래와 같은 결과를 얻는다.
[0, 0, 0, 10, 30, 0, 45, 0]
상담은 매일 하기때문에 6일에 버는 돈이 0으로 나오면 안된다.
따라서 dp[i + 1] = max(dp[i + 1],dp[i])를 해줘야 한다.
코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
static int n, s;
static int ans = 0;
static ArrayList<Pair> arr;
static int[] dp;
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
arr = new ArrayList<>();
dp = new int[n + 1];
for (int i = 0; i < n; i++) {
String[] line = br.readLine().split(" ");
arr.add(new Pair(Integer.parseInt(line[0]), Integer.parseInt(line[1])));
}
for (int i = 0; i < n; i++) {
Pair p = arr.get(i);
if (i + p.time <= n) {
dp[i + p.time] = Math.max(dp[i + p.time], dp[i] + p.pay);
}
dp[i + 1] = Math.max(dp[i + 1], dp[i]);
}
ans = dp[n];
bw.write(ans + "\n");
bw.flush();
br.close();
bw.close();
}
}
class Pair {
int time;
int pay;
public Pair(int time, int pay) {
this.time = time;
this.pay = pay;
}
}
Author And Source
이 문제에 관하여(백준 14501 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-14501-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)