[SWEA] 5215 햄버거 다이어트

SWEA.5215 햄버거 다이어트

제목 부터 어불성설이다. 햄버거 다이어트라니..

이 문제는 재귀로 풀었다. 다이나믹 프로그래밍을 이용해서 푼 사람도 있었는데, 나는 아직 dP까지 갈길이 멀다.
“선택하거나 선택하지 않는다” 라는 관점에서 접근하면 굉장히 쉬운 문제였다. 처음에 단순히 순열처럼 생각하고 접근했다가 시간초과가 발생하는걸 보고 아차 싶어 다시 풀었다. 코드에 남아있는 isSelected 가 그 흔적이다. 방문여부를 체크할 필요가 없다.

package _0208;

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

public class SW5215Hamburger {
	static int val, N, L;
	static boolean[] isSelected;
	static int[][] map;
	static String src ="";
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(new ByteArrayInputStream(src.getBytes())));
		int TC = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int testCase = 1; testCase <= TC; testCase++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken());
			map = new int[N][2];
			isSelected = new boolean[N];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				map[i][0] = Integer.parseInt(st.nextToken());
				map[i][1] = Integer.parseInt(st.nextToken());
			}
			val = combination(0, 0, 0);
			sb.append("#").append(testCase).append(" ").append(val).append('\n');
		}
		System.out.print(sb);
	}
	static int m=0;
	//cnt 번째의 재료를 고려해서 (조합에 넣을수도 안넣을 수도_) 
	//칼로리 체크후 맛점수 변경
	private static int combination(int cnt,int taste, int calorie) {
		if(calorie>L) {
			return 0;
		}
		if(calorie==L) {
			return taste;
		}
		if(cnt==N) {
			return taste;
		}
		//idx번째 재료를 사용하지 않는 경우
		int va = combination(cnt+1, taste, calorie);
		
		//idx번째 재료를 사용한 경우
		int vb = combination(cnt+1,taste+map[cnt][0],calorie+map[cnt][1]);
		
		return Math.max(va, vb);
	}

}

알고리즘을 풀면서 조금씩 BufferedReader, StringTokenizer, StringBuilder와 익숙해지고 있다.
그런데 버퍼드 리더를 사용하면 static 으로 정의한 문자열을 사용하려면 BufferArrayInputStream 을 사용해야 한다는걸 오늘 알게 되었다.
매번 테스트케이스 복붙이 귀찮아서 Scanner를 쓸때도 항상 문자열을 따로 선언하고 읽었었는데, BufferedReader에서는 BufferArrayInputStream을 추가적으로 사용해야했다.

public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
}

콘솔입력은 이렇게 입력받는다. 그런데 문자열을 선언하고 받으려면

static String src =" 아무문자열";
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(src));//불가능 에러난다.
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(new ByteArrayInputStream(src.getBytes())));
}

이렇게 해주어야한다.
아마 String은 InputStream이 아니기 때문에 InputStreamReader로 읽어들일 수 없고, 스트링을 getBytes() 메소드를 이용해서 변환한 바이트를 ByteArrayInputStream으로 읽을 수 있는것이라고 생각된다. – 나중에 IO 관련해서 정리를 한번 해야겠다.


또 버퍼드 리더를 사용할때 main 에서 thorws Exception 처리해주어야 컴파일이 가능하다. – 알고리즘 문제 풀때만 이렇게 하고, 실제 개발을 할때 메인에서 예외처리?? 어림도 없다.메인에서 던지면 누가 받지? JVM? ㅇㅅㅇ