14863번 - 서울에서 경산까지
문제 풀이 시간 : 30분
문제 풀이 :
문제를 읽자마자 dp로 풀어야겠구나 라는 생각은 했는데,
어떻게 풀어야하나 고민을 했다.
근데 N과 K가 각각 최대 100과 100,000 이었기 때문에 2차원 배열로 해서 전체 탐색을 해도 시간 안에 충분히 할 수 있겠다 라는 생각이 들었다.
그래서 2차원 배열을 만들고
가로를 시간, 세로를 도시 번호로 해서
각 도시마다 갈 수 있는 모든 경우를 계산했다.
배낭 문제와 비슷한 방식이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
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 = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[][] arr = new int[n][4];
int[][] dp = new int[n][k + 1];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
arr[i][2] = Integer.parseInt(st.nextToken());
arr[i][3] = Integer.parseInt(st.nextToken());
}
dp[0][arr[0][0]] = arr[0][1];
dp[0][arr[0][2]] = arr[0][3];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= k; j++) {
if (dp[i - 1][j] != 0) {
if(j + arr[i][0] <= k)
dp[i][j + arr[i][0]] = Math.max(dp[i - 1][j] + arr[i][1], dp[i][j + arr[i][0]]);
if(j + arr[i][2]<=k)
dp[i][j + arr[i][2]] = Math.max(dp[i - 1][j] + arr[i][3], dp[i][j + arr[i][2]]);
}
}
}
int ans = 0;
for (int i = 0; i <= k; i++) {
ans = Math.max(dp[n - 1][i], ans);
}
System.out.println(ans);
}
}무조건 정답이라는 생각으로 제출을 했는데 29점을 받았다.
그래서 문제 조건을 봤더니
1번만 만족하면 29점인 것이다.
근데 아무리 생각해도 시간초과가 날 수가 없는데,,,
라는 생각으로 질문 게시판을 조금 뒤져봤더니
2 4
2 5 2 2
2 2 2 2이런 반례가 있었다.
해당 테스트 케이스의 정답은 7이다.
근데 내 코드에서는 첫번째 도시의 경우를 dp 배열에 옮기는 과정에서 두 경우의 시간이 같은 경우를 고려하지 않았다.
dp[0][arr[0][0]] = arr[0][1];
dp[0][arr[0][2]] = arr[0][3];그래서 뒤에 나온 2가 더 큰 5를 덮어 씌운 것이다.
그래서 해당 부분을 아래와 같이 수정해주니 통과를 하였다.
dp[0][arr[0][0]] = arr[0][1];
dp[0][arr[0][2]] = Math.max(arr[0][3], dp[0][arr[0][2]]);전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
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 = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[][] arr = new int[n][4];
int[][] dp = new int[n][k + 1];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
arr[i][2] = Integer.parseInt(st.nextToken());
arr[i][3] = Integer.parseInt(st.nextToken());
}
dp[0][arr[0][0]] = arr[0][1];
dp[0][arr[0][2]] = Math.max(arr[0][3], dp[0][arr[0][2]]);
for (int i = 1; i < n; i++) {
for (int j = 0; j <= k; j++) {
if (dp[i - 1][j] != 0) {
if(j + arr[i][0] <= k)
dp[i][j + arr[i][0]] = Math.max(dp[i - 1][j] + arr[i][1], dp[i][j + arr[i][0]]);
if(j + arr[i][2]<=k)
dp[i][j + arr[i][2]] = Math.max(dp[i - 1][j] + arr[i][3], dp[i][j + arr[i][2]]);
}
}
}
int ans = 0;
for (int i = 0; i <= k; i++) {
ans = Math.max(dp[n - 1][i], ans);
}
System.out.println(ans);
}
}함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.