SWEA[5215] - 햄버거 다이어트[D3]

링크

SWEA[5215]

문제설명

• 햄버거 다이어트[D3]

문제풀이

• 그리디X, 완전탐색

문제코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{
    static int [][] item = new int [20][2];
    static int N = 0, L = 0;
    static int sum_score = 0, sum_cal = 0;
    static int ans = 0;
    static int n = 0;

    public static void Search(int n) {
        if (n == N) {
            if (ans < sum_score && sum_cal < L) {
                ans = sum_score;
            }
            return;
        }
        else {
            /*선택할경우*/
            sum_cal += item[n][1];
            sum_score += item[n][0];
            Search(n + 1);
            /*선택안할경우*/
            sum_cal -= item[n][1];
            sum_score -= item[n][0];
            Search(n + 1);
        }
    }

    public static void main(String args[]) throws Exception
    {
        //System.setIn(new FileInputStream("res/swea.d3/5215.txt"));
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            N = sc.nextInt();
            L = sc.nextInt();

            for (int i = 0; i < N; i++) {
                item[i][0] = sc.nextInt();
                item[i][1] = sc.nextInt();
            }
            /////////////////////////////////////////////////////////////////////////////////////////////
            Search(0);
            /////////////////////////////////////////////////////////////////////////////////////////////
            System.out.println("#"+test_case+" "+ans);    
            ans = 0;
        }
    }
}

문제코드 DFS

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

public class Solution5215 {
    public static int Ans=0;
    public static int Temp_Cal=0;
    public static int Temp_Score=0;
    public static int N;
    public static int L;
    public static int[][] Info;
    public static boolean[] visit;
    public static int[][] dir= {
            {1,1},
            {1,0},
            {1,-1}
    };
    public static void Search(int[]rc) {
        if(Temp_Cal>L)return;
        if(rc[0]==N) {
            Ans = Math.max(Ans, Temp_Score);
        }
        int nr=0;
        int nc=0;
        for (int i = 0; i < 3; i++) {
            nr = rc[0] + dir[i][0];
            nc = rc[1] + dir[i][1];
            if(nr>=0 && nr<=N && nc>=0 && nc<2) {
                Temp_Score += nc*Info[nr-1][0];
                Temp_Cal += nc*Info[nr-1][1];
                Search(new int[] {nr,nc});
//                원상복구
                Temp_Score -= nc*Info[nr-1][0];
                Temp_Cal -= nc*Info[nr-1][1];
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/5215.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());
            Info = new int[N][2];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                Info[i][0] = Integer.parseInt(st.nextToken());
                Info[i][1] = Integer.parseInt(st.nextToken());
            }


            Search(new int[] {0,0});


            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=0;
            Temp_Cal=0;
            Temp_Score=0;
            N=0;
            L=0;
        }//end test_case
    }//end main
}

아쉬운점

• 그리디로 접근 (14/20)
• 가성비 같은 경우도 가격낮은거 먼저 넣도록 정렬 (14/20)
• 완전탐색구조 설계가 익숙치 않았음. 모든 return으로 가는 경로를 설정하지 못했음.
• 아예 처음부터 완전탐색으로 먼저 접근 해야하나 싶음.
• Java로 재귀함수 만드는 방법 몰라서 C++로 함

잘한점

• 완전탐색으로 풀어야 한다는 것을 알았음.
• 가지치기 함 : 칼로리 제한 넘어가면 return
• Java 로 바꿈ㅎ
• DFS로 경로탐색으로 풀었음