[SWEA] 9299 한빈이와 Spot Mart

SWEA.9299 한빈이와 Spot Mart

11시에 과제를 시작해서 12전에 제출 못할까봐 초집중해서 풀었다.
다행히 이전에 풀었던 SWEA 5215 햄버거 다이어트 문제를 풀었던 것이 굉장히 도움이 되었다. 선택하거나, 선택하지 않거나에 조건식이 추가된 형태이다.
순열, 조합, 재귀와 조금씩 익숙해 지고 있는 것 같다.

package _0208;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class SW9229Snack {
	static int N, L, map[];
	static boolean[] isSelected;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int TC = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int testCase = 1; testCase <= TC; testCase++) {
			String[] s = br.readLine().split(" ");
			N = Integer.parseInt(s[0]); //과자 개수
			L = Integer.parseInt(s[1]); //Limit
			isSelected = new boolean[N];
			s = br.readLine().split(" ");
			map = new int[N];
			for (int i = 0; i < N; i++) { //N개의 과자 무게를 배열에 집어넣는다.
				map[i] = Integer.parseInt(s[i]);
			}
			int val =pick(0,0,2);
			sb.append("#").append(testCase).append(" ").append(val).append('\n');
		}//endfor
		System.out.print(sb);
	}//end main

	//과자를 골라서 최대값을 반환 하는 함수
	private static int pick(int cnt, int weight, int hands) {
		if(hands<0) { //2개를 이미 집고 또 집으려고 하는 경우 
			return -1;
		}
		if(weight>L) { //무게를 초과하는 경우 -1 리턴
			return -1;
		}
		if(hands==0) { //2번 다집은 경우
			return weight;
		}
		if(cnt==N) { // 끝까지 다 탐색한 경우
			return -1;
		}
		//과자를 고르는 경우
		int h1 = pick(cnt+1 , weight, hands);
		//과자를 고르지 않는 경우
		int h2 = pick(cnt+1 , weight+map[cnt], hands-1);
		return Math.max(h1, h2); //최대 값 반환

	}
}//end class

다른 방법들도 많이 있겠지만 아직은 재귀로 풀어보고 있다. 오늘도 읽기쉬운 코드를 작성하기 위해 노력중인데, 주석쓰는 습관이 몸에 덜 베어서 쉽지 않다. 내가 쓴 코드를 남이 봤을 때 이해하기 쉽게하려면 주석도 주석이고, 변수명을 센스있게 잘 지어야 하는것 같다.


또 알고리즘 문제를 풀 때, 항상 고정관념에서 벗어나서 최대한 창의적인 방법으로 풀어보려고 다양한 시도를 하고 있다.
물론 아무리 창의적이어도 효율적이지 못해 시간초과나, 메모리 초과가 나면 아무 의미가 없기에, 이부분도 고려해서 내가 가진 자료구조 지식들을 총 동원해서 프로그램을 짜려고 노력하고 있는데, 아직 갈길이 멀다.

특별히 자바 API관련해서 아직은 익숙하지 않은 API들이 너무 많다. JCF같은 경우나, 기본적인 메소드들이 어떤 작용을 하는지 구체적으로 알지 못하는 것들이 꽤 있어서, 앞으로 계속 블로그에 정리해나가면서 기본기를 탄탄하게 하고 나만의 직관적인 코드 스타일을 만들어 가고 싶다.