Today's Algorithm(2018-11-10)

boj 12865. 평범한 배낭

배낭 문제 참 유명하죠. 다이나믹 프로그래밍으로 풀 수 있는 대표적인 문제 중 하나인데요. 이 문제를 토대로 해결법을 정리해볼게요!

 

다이나믹 프로그래밍은 모든 수에 대해 탐색을 하는데 그 이전의 봤던 수에 나온 데이터들을 이용하는 것입니다. 중요한 것은 데이터, 즉 무엇을 기록할지입니다. 이 문제의 경우 전dp[해당_아이템][해당_무게] = 전 해당 무게에서 해당 아이템이 추가되었을 때 최고 가치로 잡아 모든 아이템을 보면서 기록해나가는 것이죠. 이 문제의 경우 다음 그림과 같이 기록 가능합니다.

그럼 의문이 들죠. '어떻게 최고 가치를 찾을 것인가?' 이전에 이렇게 구성할 때 물건을 하나씩 살펴보고 기록하기 때문에 다음과 같은 성질이 있다는 것을 알아야 합니다.

• 해당 줄의 아이템을 볼 때는 현재 아이템과 그 이전까지 비교했던 아이템들만 고려되는 것이다. 이후에 탐색될 아이템은 고려 대상이 아니다.
• 현재까지 가장 최고 가치를 가진 배낭은 바로 이전 Row의 값들이다
• 현재 아이템 무게가 나오기 전까진 비교할 필요없으므로 모두 바로 이전 Row 값들을 사용한다

이러한 성질 때문에 우리는 현재 아이템, 현재 무게에서 최고 가치가 되는 값을 찾기 위해선 바로 이전의 해당 무게를 중심으로 비교해야 합니다. 그게 현재까지 최고 가치이거든요. 그리고 그 가치와 비교될 값은 (현재 배낭 무게 - 현재 아이템 무게) + 현재가치 입니다. 그림에서 (현재 배낭 무게 - 현재 아이템 무게) + 현재가치가 보라색이고, 바로 이전 해당 무게가 초록색으로 나타내고 있습니다. 보라색이 의미하는 바는 현재 배낭 무게에 해당 아이템이 추가되었을 떄 최대 배낭 가치입니다.(그럼 당연히 현재 배낭 무게에 맞춰서 배낭 무게가 4일때랑 더해줘야겠죠. 그리고 이때 4는 물론 해당 배낭 무게에서 최대 가치값입니다). 여기서 이전 해당 무게 최대 가치가 13인데 반해 현재 아이템이 고려되었을 때는 14가 되기 때문에 더 큰 값 14로 바뀌는것이죠. 그럼 이제 코드를 볼까요?

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int itemNum = Integer.parseInt(s[0]);
        int maxWeight = Integer.parseInt(s[1]);
        int[][] dp = new int[itemNum + 1][maxWeight + 1];

        for (int i = 1; i <= itemNum; i++) {  // 처음부분은 따로 설정할 필요없게 비워있는 0인덱스 추가
            String[] ss = br.readLine().split(" ");
            int itemWeight = Integer.parseInt(ss[0]);
            int itemValue = Integer.parseInt(ss[1]);

            for (int j = 0; j <= maxWeight; j++) {
                if(j < itemWeight) {  // 해당 무게 되기전까진 앞의 무게 그대로 사용
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }

                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - itemWeight] + itemValue);
            }
        }
        System.out.println(dp[itemNum][maxWeight]);
    }
}

앞서 설명한 부분이 20번째 줄에 모두 담겨있습니다! 이해가시나요? 혹시 이해가 잘 안 가신다면 dp표를 직접 써보면서 만들어보시길 추천드립니다.

 

다른 사람 풀이를 보다가 입력을 BuffredReader로 하는 것을 보았는데요. 이전까지 Scanner를 쓰다가 이게 훨씬 빠르다고 해서 써보았습니다.

첫번째 것이 Scanner썼던 것이고 2~3번째 것이 BufferedReader썼을 때입니다. 저의 경우 약 25%정도 더 빠른것을 확인 할 수 있었는데요. 다른 블로그를 보니까 6배까지 빠른 경우도 있더라구요. 그래서 이제부터 좀 애용하려고 합니다. 알고리즘 초고수 백준님도 이렇게 사용하길 추천한다고 어디서 봤던 것 같아요!