[Java] 백준 12865 평범한 배낭 952hi의 접근방법

 

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

12865번: 평범한 배낭

 

---

 

1. 접근방법

 

배열을 여러개 사용하고 싶지 않다는 생각이 들어서 하나로 해결할 수 있는 방법을 고민했고 초기 1차원 배열을 무게만큼 생성하고 1~N개 모두 0으로 초기화한후 물건 1~M까지 차례로 끝 인덱스 부터 접근해

넣었을때 가치와 넣고 남은 무게의 가치 즉 직전 회전의 가치를 활용해 계산함

 

ex) 물건2 무게 4 총 배낭 무게 10 라면 4의 가치 X +  (10-4) => 배열의 6의 무게의 최대가치를 더해서

직전 가치보다 큰지 아닌지 판단 후 크면 갱신 아니면 다음무게로 이동하는 방식

 

2. 느낀점

 

0/1 냅섹 문제를 풀기전에는 어렵다고 생각했는데 막상 생각해보고 풀어보니 크게 어렵지 않았다.

만약에 0/1이 아니라 부셔서 넣을수 있다고 하면 굉장히 어려워 질것같다.

 

3. 코드

 

import java.io.*;

public class boj12865 {
	static class Reader {
		int bfs = 1 << 16;
		byte[] buffer = new byte[bfs];
		int bufferLeft = 0, bufferState = 0;
		DataInputStream dis = new DataInputStream(System.in);

		byte read() {
			if (bufferLeft == bufferState) {
				try {
					bufferState = dis.read(buffer, bufferLeft = 0, bfs);
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (bufferState == -1)
					buffer[0] = -1;
			}
			return buffer[bufferLeft++];
		}

		int nextInt() {
			int n = 0;
			byte b = read();
			while (b <= ' ')
				b = read();
			boolean neg = (b == '-');
			if (neg)
				b = read();
			do
				n = n * 10 + b - '0';
			while ('0' <= (b = read()) && b <= '9');
			if (neg)
				return -n;
			return n;
		}
	}
	public static void main(String[] args) {
		Reader in = new Reader();
		int m = in.nextInt();
		int wei = in.nextInt();
		int[] value = new int[wei+1];
		int comp[][] = new int[m][2];
		for(int i=0;i<m;i++) {
			comp[i][0] = in.nextInt();
			comp[i][1] = in.nextInt();
		}
		int temp;
	out:for(int k=0;k<m;k++) {//물건 기준
			for(int i=wei;i>0;i--) {//무게 기준
				if(i - comp[k][0]<0) continue out; // 배열 인덱스 오류 해결
				temp = comp[k][1]+value[i-comp[k][0]]; 
                // 배낭에 내 물건과 직전에 내물건을 넣고 남은 무게만큼 넣을수 있는 가치의 합 
				if(temp>value[i]) {// 가치가 크면 갱신
					value[i] = temp;
				}
			}
		}
		System.out.println(value[wei]);
	}
}

 

4. 메모리 및 시간