[BOJ/JAVA] 백준 7579번 : 앱

7579번: 앱

---

 

• 생각

문제를 푼 계기) 무심코 알고리즘 분류를 눌렀다가 배낭문제가 적힌 것을 봐버렸다. 배낭문제 풀 때도 완벽하게 이해하고 풀지 않았던 것 같아서 비슷한 문제를 풀어봐야겠다고 생각했다.

 

1. dfs로 파라미터를 (현재까지 확보된 메모리 용량, 메모리에 따른 비용)을 보내면서 돈다. basecase론 확보된 용량이 원해는 용량보다 클 경우로 둔다.  ==>> 시간초과

 

 

2. dp 배열을 통해 해결하는 방법이 있다. 해결 방법은 해당 메모리를 dp[비용] = 최대 메모리로 채워 넣는 방법이다. 

 

 

• 코드

정답 코드 : dp 배열을 통해 가장 큰 메모리부터 j-cost인덱스 dp배열에 cost인덱스 에 맞는 메모리를 더 했을때 더 크면 dp배열을 초기화 시키는 방법이다. 이렇게해주면 최종적으로 dp 배열엔 dp[비용] = 최대 메모리가 들어있다.

 

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
	static int N,M, minMemory;
	static int[] usingByteOfMemory, disabledByteOfMemory, dp;

	public static void main(String[] args) throws Exception {
		SetData();	
		minMemory = ReturnMinMemory();
		System.out.println(minMemory);
	}

	// 데이터
	private static void SetData() throws Exception  {
		InputReader in = new InputReader(System.in);
		
		N = in.readInt();
		M = in.readInt();
		
		usingByteOfMemory = new int[N];
		disabledByteOfMemory = new int[N];
		dp = new int[10001];
		Arrays.fill(dp, -1);
		minMemory = Integer.MAX_VALUE;
		
		for(int i = 0; i < N; i++)
			usingByteOfMemory[i] = in.readInt();
		
		for(int i = 0; i < N; i++)
			disabledByteOfMemory[i] = in.readInt();
	}
	
	private static int ReturnMinMemory() {		
		
		// dp[i]: i cost를 써서 확보할 수 있는 최대 메모리
		for(int i=0; i<N; i++){
			int cost = disabledByteOfMemory[i];
			// 뒤에서 부터 확인해야 겹치지 않고 값을 update 할 수 있다.
			for(int j=10000; j>=cost; j--){
				if(dp[j-cost] != -1){
					// 이전 j-cost 까지의 최대 값에 현재 memory를 더하는게 더 크다면 update
					if(dp[j-cost] + usingByteOfMemory[i] > dp[j])
						dp[j] = dp[j-cost] + usingByteOfMemory[i];
				}
			}
			// 메모리 업데이트가 안되어있는 경우 업데이트
			// 단 메모리가 더 큰 경우에만 업데이트 가능
			if(dp[cost] < usingByteOfMemory[i]) dp[cost] = usingByteOfMemory[i];
		}

		for(int i=0; i<10001; i++){
			// 최소 메모리 return
			if(dp[i] >= M){
				return i;
			}
		}
		return 0;
	}
    
	private static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public int readInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			if (filter != null) {
				return filter.isSpaceChar(c);
			}
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}