JAN's History
10주차_백준 문제풀이 본문
목차
- 12865
- 2565
- 1149
문제 12865
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
static Integer[][] dp;
static int[] W; // weight
static int[] V; // value
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());
W = new int[N];
V = new int[N];
dp = new Integer[N][K + 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
W[i] = Integer.parseInt(st.nextToken());
V[i] = Integer.parseInt(st.nextToken());
}
System.out.println(knapsack(N - 1, K));
}
static int knapsack(int i, int k) {
// i가 0미만, 즉 범위 밖이 된다면
if (i < 0)
return 0;
// 탐색하지 않은 위치라면?
if (dp[i][k] == null) {
// 현재 물건(i)을 추가로 못담는 경우 (이전 i값 탐색)
if(W[i] > k) {
dp[i][k] = knapsack(i - 1, k);
}
// 현재 물건(i)을 담을 수 있는 경우
else {
// 이전 i값과 이전 i값에 대한 k-W[i]의 값 + 현재 가치(V[i])중 큰 값을 저장
dp[i][k] = Math.max(knapsack(i - 1, k), knapsack(i - 1, k - W[i]) + V[i]);
}
}
return dp[i][k];
}
}
해설
이 문제는 "DP[물건 인덱스 고려][가방무게] = 가방에 담긴 가치" 로 테이블을 만들어보면 알고리즘을 확인할 수 있다.
dp 0~7은 가방무게, i는 물건의 개수라고 가정해보자.
문제에서는 물품의 수가 4개이고, 최대 넣을 수 있는 무게가 7K이기 때문에 테이블을 작성하면 위와 같다.
먼저 무게 W[] 배열과 가치 V[] 배열이 있다고 할 때, 각 W[i] 의 무게에 대응되는 가치는 V[i]다. 즉, (Wi, Vi) 라고 할 때, 위 예제로는 다음과 같다.
(Wi, Vi) = (6, 13), (4, 8), (3, 6), (5, 12)
그리고 배낭이 수용 가능한 최대 무게 K = 7 이다.
i=1부터 탐색할 때, i=1에는 (6, 13)으로 가방무게가 6일 때 가치가 13이 된다.
i=2는 (4, 8)이므로 무게가 4일 때 가치가 8이 되고, 6일 때엔 13이 된다.
그리고 (7 - W[2]) 무게에 대한 이전 i값, 즉 (7 - 4) = 3이고, 3이라는 무게에 대응되는 i = 1 일 때의 값(빨간색 박스)은 0이다 이 둘을 합하면 8이 되고, 8과 13 중 최댓값은 13이므로 13이 저장된다.
i=3일 때에는 (3, 6)이므로 먼저 이전 dp[7] 일 때의 i=2의 값 13을 갖고온다. 그리고 다른 조합방법을 탐색하기 위해
현재 i = 3 은 (3, 6)이고 가치는 6이다. 그리고 (7 - W[3]) = (7 - 3) = 4이고 4에 대응되는 i = 2의 가치는 가치는 8이다. 즉, 6 + 8 = 14가 되고, 이전 i값보다 큰 값이므로 최댓값 14가 저장된다. 즉, 아래와 같다.
i = 4 일 때 가치는 (5, 12) 로 12 이고, (7 - W[5]) = 2로, 2에 대응하는 무게는 0이다. 즉 합은 12이인데, 이전 값 14 보다 작기 때문에 12가 아닌 14가 저장되는 것이다.
이를 토대로 재귀문(Top-Down 방식)을 만들 수 있다.
static int knapsack(int i, int k) {
// i가 0미만, 즉 범위 밖이 된다면
if (i < 0)
return 0;
// 탐색하지 않은 위치라면?
if (dp[i][k] == null) {
// 현재 물건(i)을 추가로 못담는 경우 (이전 i값 탐색)
if(W[i] > k) {
dp[i][k] = knapsack(i - 1, k);
}
// 현재 물건(i)을 담을 수 있는 경우
else if (W[i] <= k) {
// 이전 i값과 이전 i값에 대한 k-W[i]의 값 + 현재 가치(V[i])중 큰 값을 저장
dp[i][k] = Math.max(knapsack(i - 1, k), knapsack(i - 1, k - W[i]) + V[i]);
}
}
return dp[i][k];
}테이블에서 최대값을 결정하는 방법이 두가지인데
1. 현재 물건을 선택하지 않는 경우 => 윗칸에서 가져옴
2. 현재 물건을 선택하는 경우 => [이전물건 선택][남아 있는 무게]
이를 코드화 하면 max(knapsack(i - 1, k), knapsack(i - 1, k - w[i]) + v[i]);가 된다.
문제 2565
코드
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
public class Main {
static Integer[] dp;
static int[][] wire;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
dp = new Integer[N];
wire = new int[N][2];
for(int i = 0; i < N; i++) {
wire[i][0] = in.nextInt();
wire[i][1] = in.nextInt();
}
// 첫 번째 원소(A전봇대)를 기준으로 오름차순으로 정
Arrays.sort(wire, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int max = 0;
/*
* i번째 A전봇를 기준으로 연결가능한 개수 탐색
* 및 최댓값 찾기
*/
for(int i = 0; i < N; i++) {
max = Math.max(recur(i), max);
}
// 전선 개수 - 쵀댓값
System.out.println(N - max);
}
static int recur(int N) {
// 탐색하지 않았던 위치라면
if(dp[N] == null) {
dp[N] = 1; // 최솟값 1로 초기화
// A의 N번째와 이후의 전봇대들 비교
for(int i = N + 1; i < dp.length; i++) {
/*
* A전봇대의 N번째 전선이 연결되어있는 B전봇대보다 A의 i번째
* 전봇대의 전선이 이어진 B전봇대가 뒤에 있을 경우
* 전선을 설치할 수 있음
*/
if(wire[N][1] < wire[i][1]) {
// 연결 가능한 전선의 경우의 수 중 큰 값을 dp에 저장한다.
dp[N] = Math.max(dp[N], recur(i) + 1);
}
}
}
return dp[N];
}
}
풀이
철거되어야 할 전선의 최소 개수라 하면, 거꾸로 전체 전선의 개수에서 최대한 겹치지 않게 설치 가능한 개수를 구하여 빼면, 즉 (전체 전선 개수 - 설치 가능 개수) = 철거 개수 가 되지 않을까?
먼저 A와 B전봇대를 의미하는 2차원 배열과 메모이제이션 할 배열 두 가지가 필요하겠다. wire배열을 선언할 건데, wire[N][0] 이 A전봇대, wire[N][1] 이 B전봇대다. 또한 dp의 경우 방문 여부를 편하게 판단하기 위해 Integer 객체 배열로 선언했다.
int[][] wire = new int[N][2];
Integer[] dp = new Integer[N];그리고 wire에 입력을 받았다는 가정하에, wire배열을 A전봇대 기준으로 정렬해야하된다. Arrays.sort() 메소드 자체에는 2차원 배열을 정렬해주는 것이 없으므로 comparator를 이용하여 다음과 같이 정렬한다.
int[][] wire = new int[N][2];
Integer[] dp = new Integer[N];
Arrays.sort(wire, Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});재귀로 풀려면 먼저 A전봇대의 탐색 기준값을 중심으로 B에 연결할 때 이전에 B에 연결된 전봇대 값보다 커야한다. 그래야 겹치지 않게 할 수 있지 않겠는가. 즉, N+1부터 마지막 까지 A전봇대를 기준으로 탐색하면서 B전봇대에 연결 가능 한지 여부를 확인하고, 연결 가능하다면 그 다음에 연결할 전선을 탐색하기 위해 재귀를 해주는 것이다.
static int recur(int N) {
// 탐색하지 않았던 위치라면
if(dp[N] == null) {
dp[N] = 1; // 최솟값 1로 초기화
// A의 N번째와 이후의 전봇대들 비교
for(int i = N + 1; i < dp.length; i++) {
/*
* A전봇대의 N번째 전선이 연결되어있는 B전봇대보다 A의 i번째
* 전봇대의 전선이 이어진 B전봇대가 뒤에 있을 경우
* 전선을 설치할 수 있음
*/
if(wire[N][1] < wire[i][1]) {
// 연결 가능한 전선의 경우의 수 중 큰 값을 dp에 저장한다.
dp[N] = Math.max(dp[N], recur(i) + 1);
}
}
}
return dp[N];
}문제 1149
코드
import java.util.Scanner;
public class Main {
final static int Red = 0;
final static int Green = 1;
final static int Blue = 2;
static int[][] Cost;
static int[][] DP;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
Cost = new int[N][3];
DP = new int[N][3];
for(int i = 0; i < N; i++) {
Cost[i][Red] = in.nextInt();
Cost[i][Green] = in.nextInt();
Cost[i][Blue] = in.nextInt();
}
// DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
DP[0][Red] = Cost[0][Red];
DP[0][Green] = Cost[0][Green];
DP[0][Blue] = Cost[0][Blue];
System.out.print(Math.min(Paint_cost(N- 1, Red), Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue))));
}
static int Paint_cost(int N, int color) {
// 만약 탐색하지 않은 배열이라면
if(DP[N][color] == 0) {
// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
if(color == Red) {
DP[N][Red] = Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue)) + Cost[N][Red];
}
else if(color == Green) {
DP[N][Green] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Blue)) + Cost[N][Green];
}
else {
DP[N][Blue] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Green)) + Cost[N][Blue];
}
}
return DP[N][color];
}
}
풀이
일단 각각의 집을 색칠해야하고, 색의 종류는 3가지가 주어진다 (빨간색, 초록색, 파란색). 그리고 각 집마다 해당 색을 칠하는 비용이 주어진다. 그리고 전체 집을 색칠 할 때 최소 비용을 구하는 것이다.
이때 중요한 점이라면 인접한 집끼리는 색이 겹치면 안된다는 점이다.
예로들어 3번 집에 초록색을 칠한다면, 2번집과 4번집은 초록색을 칠 할 수 없다. 이러한 조건으로 인해 주로 실수하는 점이 비용을 구할 때 그냥 최솟값만을 찾아서 하면 틀린다.
1번 집 최솟값 = 1,
인접한 집끼리는 같은 색을 칠 할 수 없으므로 2번 집의 초록색과 파란색 중 최솟값을 찾아 누적합. 즉 103 + 1
이전 집이 초록색이였으므로 빨간색 집과 파란색 집 중 최솟값을 누적합. 즉 100 + 104
즉, 위와같이 하면 출력은 204가 되겠지만 이게 정답인가?
아니다.
사실 정답은 100(1번집 Green) + 1(2번집 Red) + 1(3번집 Green)인 102가 정답이다. 즉 각 집별 최솟값이 아닌 아래 그림과 같은 빨간색 칸을 선택해야 올바른 정답이 된다.
결과적으로 각 집의 최솟값을 찾아 누적합을 구하는 것이 아닌 모든 경로의 경우의 수를 찾아서 최종적으로 작은 누적합을 찾아야 한다.
각 집의 비용을 Cost라고 할 때 이를 한 단계씩 적어보면 다음과 같다. (이때 min은 두 개의 값 중 최솟값을 의미하며 += 은 누적합이다.)
각 집의 비용을 Cost라고 할 때 이를 한 단계씩 적어보면 다음과 같다. (이때 min은 두 개의 값 중 최솟값을 의미하며 += 은 누적합이다.)
즉, 점화식으로 본다면 N에 대하여 세 가지 케이스에 대해 다음과 같다.
Red일 경우
Cost[N][0] = min( Cost[N-1][1], Cost[N-1][2] ) + Cost[N][0]
Green일 경우
Cost[N][1] = min( Cost[N-1][0], Cost[N-1][2] ) + Cost[N][1]
Blue일 경우
Cost[N][2] = min( Cost[N-1][0], Cost[N-1][1] ) + Cost[N][2]
기본적으로 이전의 문제들 (01타일, 피보나치 수 등..)과 같은 알고리즘을 사용하면 된다. 다만 3가지 케이스를 이용해야하니 Cost[][] 배열과, 탐색하면서 누적합을 저장할 DP[][] 함수를 두면 된다. 그리고나서 위 점화식을 이용하여 재귀함수로 구성한 뒤, 해당 배열을 아직 탐색하지 않았다면 재귀를 해주고, 그 외의 경우는 DP배열의 값을 반환해주면 된다.
int[][] Cost = new int[N][3]; // 이미 입력값들로 초기화가 되었다고 가정
int[][] DP = new int[N][3];
// DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
DP[0][Red] = Cost[0][Red];
DP[0][Green] = Cost[0][Green];
DP[0][Blue] = Cost[0][Blue];
static int Paint_cost(int N, int color) {
// 만약 탐색하지 않은 배열이라면
if(DP[N][color] == 0) {
// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
if(color == Red) {
DP[N][Red] = Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue)) + Cost[N][Red];
}
else if(color == Green) {
DP[N][Green] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Blue)) + Cost[N][Green];
}
else {
DP[N][Blue] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Green)) + Cost[N][Blue];
}
}
return DP[N][color];
}
'백준' 카테고리의 다른 글
| 14주차_백준 문제풀이 (0) | 2023.08.11 |
|---|---|
| 12주차_백준 문제풀이 (0) | 2023.07.22 |
| 9주차_백준 문제풀이 (0) | 2023.06.24 |
| 8주차_백준 문제풀이 (0) | 2023.06.18 |
| 7주차_백준 문제풀이 (0) | 2023.05.28 |
