코드트리 [자바 java] 둘 중 하나 잘 고르기

https://www.codetree.ai/missions/2/problems/choose-one-of-two-points?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

꼭 n개를 뽑아야 한다 같은 유형의 dp를 푸는 방식을 사용했다.

이 문제에서는 n개의 카드 짝이 주어지고, 이 카드들 중 빨강, 파랑 을 정확히 n번 씩 사용했을 때 카드의 합의 최댓값을 구해야 한다.

 

위와 같이 주어졌다고 가정해보자. 위 4가지 카드 중 빨강, 파랑을 각각 2개씩 뽑아야 한다.

이를 풀기 위해 dp배열을 만들었다. 이 배열에서 i는 현재 탐색중인 카드 짝의 번호를 의미하고, j는 현재 뽑은 카드 중 빨강색의 갯수를 의미한다.

이 문제에서는 모든 값이 양수라서 dp에 최솟값을 따로 넣을 필요가 없지만, 만약 음수도 입력된다면 최솟값을 꼭 모든 값에 입력해야한다.

 

dp[0][0]는 아무 카드도 뽑지 않는 경우이므로 0을 넣었다. 

dp를 채울 때에는 위와 같이 두 가지 상황을 고려해야 한다.

보라색은 빨간 카드를 쓰는 경우의 수가 하나 증가했으니, 빨간 카드를 정한 것을 의미한다.

초록색은 빨간 카드를 쓰는 경우의 수가 증가하지 않았으니 파란 카드를 정한 것을 의미한다. 이 때  dp값은 최댓값을 구해야하므로 위 두 경우 중 더 큰 값을 넣으면 된다. 

 

여기서 예외처리를 해야 하는 부분이 있는데, 

• j값이 0이라서 빨간색 카드를 사용할 수 없는 경우
• 이제까지 탐색한 카드의 수가 j와 같을 때 ( 그럼 이전 짝에서 고른 카드의 수가 j보다 많았다는 모순이 발생하므로)

이를 잘 고려해서 dp를 채우고, 다 채운 배열에서 제일 오른쪽 하단의 값이 모든 카드를 탐색했고, 빨간색의 수가 n개인 경우중 최댓값이므로 답이 된다.

 

import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st;


        int[] a = new int[n*2+1];
        int[] b = new int[n*2+1];

        for(int i = 1;i<=2*n;i++){
            st = new StringTokenizer(br.readLine());
            a[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[2*n+1][n+1];
        dp[0][0] = 0;


        for(int i = 1;i<=2*n;i++){
            for(int j = 0;j<=n;j++){
                if(j == 0) dp[i][j] = dp[i-1][j] + b[i]; // 빨간색을 0번 사용하는 경우
                else if(j == i) dp[i][j] = dp[i-1][j-1] + a[i]; //현재 탐색하는 카드 수보다 i가 더 많을 때
                else dp[i][j] = Math.max(dp[i-1][j-1] + a[i], dp[i-1][j] + b[i]);
            }
        }

        System.out.println(dp[2*n][n]);

    }
}

i == j일 때 의 경우를 고려하지 않아서 틀렸습니다가 나왔다.