[DFS] 3. 최대점수 구하기

<<풀이>>

 

-나의 풀이-

 

 

이번 DFS는 맞췄다 !! ㅎㅎ 계속하다보니깐 어떤 원리로 돌아가는지 파악이 되고 조금 더 수월하게 접근할 수 있었다.

 

전체적인 흐름

접근 방식은 DFS이고, 이 역시 더하냐 빼냐 두 가지로 최종 값 2^n 의 형태로 진행하는 것이다.

우선은 노드를 연산한 값으로 생각했다. 그리고 더하고 빼는 것을 간선으로 여기고 접근을 했다.

그렇게 해서 시간이 오버가 되면 return 시켰다. 그리고 총 배열의 행 갯수만큼 돌면 최종적으로 Math.max로 

비교하여 answer를 갱신했다.

 

import java.util.Scanner;

class Main {
    static int answer;

    private void DFS(int L, int a, int m, int total, int[][] arr) {
        if (a > m) return;
        if (L == arr.length - 1) {
            answer = Math.max(answer, total);
            return;
        } else {
            L++;
            DFS(L, a + arr[L][1], m, total + arr[L][0], arr);
            DFS(L, a , m, total, arr);
        }
    }
    
    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int L = 0;

        int[][] arr = new int[n + 1][2];

        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < 2; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        T.DFS(L, arr[0][0], m, 0, arr);
        System.out.println(answer);
    }
}

 

 

-강사님 풀이-

 

import java.util.Scanner;

class Main {
    static int answer=Integer.MIN_VALUE, n, m;

    private 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 in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        int[] a = new int[n];
        int[] b = new int[m];

        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
            b[i] = in.nextInt();
        }


        T.DFS(0, 0, 0, a, b);
        System.out.println(answer);
    }
}

 

역시나 강사님은 나랑 풀이 방식은 같지만 훨씬 더 잘 정리해서 작성했다 ㅋㅋ

 

나는 2차원배열을 생각했지만 어차피 특정 인덱스에 들어가야 할 값들이 고정되어 있다면 그냥 

배열 두 개를 만들어줘서 순서에 맞게 넣어주면 되는 것이다.

 

나머지 논리적인 접근 방식은 동일하다. 

 

*L++과 L + 1 은 같은 결과를 가져올 수도 있지만, L자체가 새로 갱신되는 것은 L++만 가능하고 L + 1은 다시 L = L + 1을 해야한다.