백준 JAVA 2798 블랙잭 리뷰 dfs/3중for문

문제풀이

기본적인 완전탐색 문제였다. 카드가 n개 주어질때 1~n 수의 카드가 주어진게 아니라서 카드를 배열에 넣고 dfs 재귀호출을 통해 카드를 불러 풀었다. 다른 풀이를 보니 3중 for문도 가능했다. 3중 for문은 카드가 1~n의 수 카드가 주어질때만 가능한 줄 알았는데 아니었다. 아직 완전탐색 문제를 많이 풀지 않아서 개념이 부족하다. 문제를 많이 풀어야겠다

dfs 풀이와 3중 for문 풀이 두 개 올린다.

 

dfs

처음에 dfs 안에 if문에 cnt<3과 sum<=m 조건을 넣었는데 그렇게 하니 값이 제대로 안 나왔다.

다른 풀이를 보면서 for문 앞에 조건들을 넣어야한다는 것을 배웠다.

import java.util.*;

public class Main{
    static int[] arr;
    static boolean[] visited;
    static int ans,sum,n,m;
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
         n = scan.nextInt();
         m=scan.nextInt();
        arr =new int[n];
        visited=new boolean[n];
        for(int i=0;i<n;i++){
            arr[i]=scan.nextInt();
        }

        dfs(0,0);
        System.out.println(ans);
    }
    static void dfs(int cnt,int sum){

        for(int i=0; i<n;i++){
            if(cnt==3){
                if(sum<=m) {
                    ans = Math.max(sum, ans);
                }
                return;
            }
            if(!visited[i]){
                visited[i]=true;
                dfs(cnt+1,sum+arr[i]);
                visited[i]=false;
            }
        }

    }
}

 

3중 for문

배열에 넣고 인덱스를 기준으로 3중 for문 돌리면 된다. 그러면 카드 숫자 상관없이 구할 수 있다.

3중 for문으로 모든 3개의 카드 조합이 만들어진다. 만들어지면 temp에다 카드 숫자들 합해서 비교하면 된다.

 

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int n = scan.nextInt();
        int m=scan.nextInt();
        int[] arr =new int[n];
        for(int i=0;i<n;i++){
            arr[i]=scan.nextInt();
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<n;k++){
                    int temp = arr[i] + arr[j] + arr[k];
                    if(temp<=m){
                        ans=Math.max(temp,ans);
                    }
                }
            }
        }
        System.out.println(ans);
    }
}