[문제풀이] 08-03. 최대 점수 구하기

인프런, 자바(Java) 알고리즘 문제풀이#### 인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0803. 최대 점수 구하기(DFS)

🗒️ 문제

🎈 나의 풀이

	 private static int m, maxScore = 0;
    private static int[] ch;
    private static class P {
        int score;
        int time;

        public P(int score, int time) {
            this.score = score;
            this.time = time;
        }
    }
    private static void DFS(int n,  List<P> list) {
        if(n >= list.size()) return;
        int sum = 0;
        int time = 0;

        for(int i=0; i<list.size(); i++) {
            if(ch[i] == 0) {
                P p = list.get(i);
                if(time + p.time > m) break;
                time+= p.time;
                sum+= p.score;
            }
        }

        maxScore = Math.max(maxScore, sum);

        ch[n] = 1;
        DFS(n+1, list);
        ch[n] = 0;
        DFS(n+1, list);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        m = sc.nextInt();
        List<P> list = new ArrayList<>();
        ch = new int[n];

        for(int i=0; i<n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            list.add(new P(a, b));
        }
        DFS(0, list);
        System.out.println(maxScore);
    }

🖍️ 강의 풀이

  	static int answer=Integer.MIN_VALUE, n, m;
	boolean flag=false;
	public void DFS(int L, int sum, int time, int[] ps, int[] pt){
		if(time>m) return;
		if(L==n){
			answer=Math.max(answer, sum);
		}
		else{
			DFS(L+1, sum+ps[L], time+pt[L], ps, pt);
			DFS(L+1, sum, time, ps, pt);
		}
	}

	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();
		int[] a=new int[n];
		int[] b=new int[n];
		for(int i=0; i<n; i++){
			a[i]=kb.nextInt();
			b[i]=kb.nextInt();
		}
		T.DFS(0, 0, 0, a, b);
		System.out.println(answer);
	}

💬 짚어가기

해당 문제는 이전에 풀이한 강아지 승차와 로직이 같으며, DFS를 이용하여 풀 수 있다.

나의 풀이에서는 클래스를 생성하여, 문제의 점수와 풀이 시간을 하나의 객체에 담아서
사용할 수 있도록 하였다.

강의에서도 이전 문제와 동일한 로직으로 풀이하였고, 문제의 점수와 풀이 시간을 각각
배열에 담아서 같은 인덱스로 접근하도록 구현하였다.