[Algorithm] 백준 DP문제 - 상자넣기(1965) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 

이번 포스팅은 백준 DP문제 - 상자넣기 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1965

1965번: 상자넣기

 

1. 풀이 소스

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            box.setMap(i, parseInt(st.nextToken()));
        }

        box.run();
        System.out.println(box.getResult());
    }

}

class Box {
    int n;
    int[] map; // 값 저장
    int[] dp; // 최대 몇개를 넣을 수 있는지 저장하는 DP
    int result;
    public Box(int n) {
        this.n = n;
        map = new int[n];
        dp = new int[n];
    }

    public void setMap(int i, int value) {
        map[i] = value; // 0: 값
    }

    int getResult() {
        return result;
    }

    public void run() {
        dp[0] = 1; // 첫 번째 선택은 1

        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (map[j] < map[i]) { // 만약 현재 있는 상자의 값보다 적다면
                    dp[i] = Math.max(dp[j], dp[i]); // 그 적은 상자와 현재 dp를 비교하여 업데이트
                }
            }
            dp[i] += 1; // 자기 자신을 넣어야 하므로 +1
            result = Math.max(dp[i], result);
        }
    }
}

 

2. 풀이 중점 사항

 

현재 A라는 위치에 있는 상자를 기준으로 가장 많이 넣을 수 있는 경우를 판단하려면 

1 2 3 ~ A - 1까지 상자를 순회하며 몇 개의 상자를 넣을 수 있는지 판단해야 합니다. 

만약 1 5 3 7 이라는 상태가 주어졌고,

7에 넣을 수 있는 상자를 판단하려면 

1 , 5 넣거나 안넣거나, 만약 5가 있다면 3 X, 5가 없다면 3 O 이러한 식으로 복잡한 구성이 되어야 합니다.

 

이러한 문제를 해결하기 위한 방법이 DP를 활용하는 것입니다.

 

dp[0] = 1; // 첫 번째 선택은 1

먼저, 0번째 인덱스, 즉 첫 번째 원소를 상자에 넣어서 값이 최대가 되는 방법은 무조건 자기 자신을 넣는 것입니다.(자기 자신과 크기가 같은 상자가 있으므로)

 

for (int i = 1; i < n; i++) {
    for (int j = i - 1; j >= 0; j--) {
        if (map[j] < map[i]) { // 만약 현재 있는 상자의 값보다 적다면
            dp[i] = Math.max(dp[j], dp[i]); // 그 적은 상자와 현재 dp를 비교하여 업데이트
        }
    }
    dp[i] += 1; // 자기 자신을 넣어야 하므로 +1
    result = Math.max(dp[i], result);
}

map은 값을 저장하는 배열입니다. 1 5 3 7 을 map에 각각 인덱스에 맞게 넣는 것입니다.

dp는 각 인덱스에 최대 몇 개를 넣을 수 있는지를 판단하는 것입니다.

map과 dp를 함께 보면, map[i]에 있는 값을 가진 상자에 최대 몇 개의 상자를 넣을 수 있는지를 dp[i]에 기록하는 것입니다.

 

5 => index 1이므로,

if (map[0] < map[1]) :

    dp[i] = Math.max(dp[0], dp[1]) 

 

dp[i] += 1

 

이전 dp의 최대이면서, 자기 자신보다 값이 작은 상자를 골라 하나를 더해주는 로직을 완성할 수 있습니다.

 

이상으로 상자넣기 자바 풀이를 마치도록 하겠습니다. 감사합니다.!