SWEA 5215번 - 햄버거 다이어트

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT 

SW Expert Academy

 

 

 

 

 

실패 코드 - 모든 tc 통과x

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

public class Solution {
	static int N, L;
	static int[] T, K;
	static boolean[] visited;
	static int[] result; //조합 결과(인덱스 저장)
	static int max = 0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int TC = Integer.parseInt(br.readLine());
		
		for(int tc = 1; tc <= TC; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			N = Integer.parseInt(st.nextToken());
			L = Integer.parseInt(st.nextToken()); //제한 칼로리
		
			T = new int[N]; //맛 점수
			K = new int[N]; //칼로리
			
			for(int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				
				T[i] = Integer.parseInt(st.nextToken());
				K[i] = Integer.parseInt(st.nextToken());
			}
			
			visited = new boolean[N];
			
			for(int i = 1; i <= N; i++) {
				result = new int[i];
				combination(0, 0, i); //n개 조합
			}
			
			//출력
			System.out.println("#" +  tc + " " + max);
		}

	}

	public static void combination(int start, int depth, int n) {
		if(depth == n) {
			int scoreSum = 0;
			int calSum = 0;
			
			for(int i = 0; i < result.length; i++) {
				scoreSum += T[result[i]];
				calSum += K[result[i]];
			}
			
			if(calSum <= L) {
				max = Math.max(max, scoreSum);
			}
			
			return;
		}
		
		for(int i = start; i < N; i++) {
			if(visited[i]) continue;
			
			visited[i] = true;
			result[depth] = i; //인덱스를 저장
			combination(i + 1, depth + 1, n);
			visited[i] = false;
		}
		
	}
}

 

 

 

 

 

알고보니 테케 안에서 max = 0으로 초기화를 안해줬다.....

 

저렇게 조합으로 풀 수도 있지만, 부분 집합으로도 풀 수 있다.

 

 

 

 

다른 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int N, L;
    static int[] T;
    static int[] K;
    static int max;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
        int TC = Integer.parseInt(br.readLine());
         
        for(int tc = 1; tc <= TC; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
             
            N = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken()); //제한 칼로리
         
            T = new int[N]; //맛 점수
            K = new int[N]; //칼로리
             
            for(int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                 
                T[i] = Integer.parseInt(st.nextToken());
                K[i] = Integer.parseInt(st.nextToken());
            }
             
            max = 0;
            dfs(0, 0, 0);
             
            //출력
            System.out.println("#" + tc + " " + max);
        }
 
    }
 
    public static void dfs(int depth, int score, int cal) {
        if (cal > L) return;
         
        if(depth == N) {
            max = Math.max(max, score);
            return;
        }
         
        dfs(depth + 1, score + T[depth], cal + K[depth]); //재료 포함
        dfs(depth + 1, score, cal); //재료 포함x    
    }
}