[BaekJoon] 12865 평범한 배낭 (java)

🔗 문제 링크

https://www.acmicpc.net/problem/12865

📝 문제 풀이 방법

해당 문제는 대표적인 DP(Dynamic Programming)문제로 배열을 이용하여 Bottom-up방식으로 문제를 해결해야한다.

문제를 풀기 위해서는 무게 K의 크기로 배열을 생성하고 각 무게당 만들 수 있는 최대의 가치를 저장하도록 해야한다.

아래의 표는 첫 줄은 아무 물건도 넣지 않았을 때의 초기 상태를 의미하며 2번째 줄부터는 input값에서 주어진 물건을 하나씩 넣었을 때를 계산한 값이다.

2번째 줄을 보면 무게 6에 가치 13인 물건을 넣어 무게 6의 기존에 가치 0보다 더 큰 값이라13으로 업데이트를 해준다. 또한 무게 7은 무게 6과 무게 1을 합쳐서 만들 수 있어서 그 둘을 합한 결과 13이라는 기존 0보다 더 큰 값이 나와 13으로 업데이트를 해준다.

이와 같이 각각의 input값에 대해서 해당 물건을 나왔을 때 가치가 커지는 값들이 있으면 값을 업데이트 하며 진행을 하면 최종 결과를 얻을 수있다.

👨🏻‍💻 1차원 배열로 작성한 코드 (실패)

해당 문제의 해설 및 다른 사람의 풀이를 보면 모두 2차원 배열을 사용하였다.
하지만 이러한 풀이에서 n-1번째 row만을 사용하여 n번째 row를 생성하는 구조는 너무 비효율적이라 생각하여 처음에 1차원 배열로 문제를 풀어봤다.. 하지만 테스트 케이스로 중간 과정과 결과는 옳은 결과가 나오나 답안 제출을 하면 실패했다는 결과를 받았다..

이유를 알고 싶습니다..아시는 분 있으시면 댓글 부탁드립니다😥

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		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[k+1]; // k개의 배열이 필요하나 index계산을 쉽게 하기 위해 k+1개 생성
		
		for (int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			
			for (int j=w; j<=k; j++) {
				if(arr[j] < v+arr[j-w]) 
					arr[j] = v+arr[j-w];
			}

		}	
		System.out.println(arr[k]);
	}
}

👨🏻‍💻 2차원 배열로 작성한 코드 (통과)

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		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+1][k+1]; // k개의 배열이 필요하나 index계산을 쉽게 하기 위해 k+1개 생성
		
		for (int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			
			for (int j=1; j<=k; j++) {
				arr[i][j] =j < w? arr[i-1][j] : Math.max(v+arr[i-1][j-w], arr[i-1][j]);
			}
		}
		
		System.out.println(arr[n][k]);
	}

}