Javaアルゴリズム(DFS,BFS利用)

に質問

解決策

この問題ではcheck配列は使用されません.すべての条件を検索するので、含むか含まないかを検索します.

注意事項

コード#コード#

package inflearn.section8_dfs_bfs활용;
// 합이 같은 부분집합
// dfs
// 포함한다 안한다로 넓힘
// 1 3 5 6 7 10 -> 여기선 10까지 다 들어가는것을 의미
// 끝나는 조건은 언제까지? -> level이 다 다르면 끝, level은
// 입력 값
// 6 (개수)
// 1 3 5 6 7 10

import java.util.*;
public class 합이같은부분집합 {
    static int n;
    static int arr[]; // 해당 노드 방문 여부는 필요 없음. -> OX로 나누는 것이기 때문에 나누어짐
    static String answer="NO";
    static int sum;
    static boolean flag=false;

    public void dfs(int l, int hap) {

        if (flag) return;
        if (l==n) { // 헷갈리면 1개만 사용할때를 생각해보자
            if ((sum-hap)==hap) { // 전체 토탈에서 빼준다. /2로 하면 합이 125같은 홀수 일때 문제, 125/2==62가 되어버림
                answer="YES";
                flag=true;
            }
        }
        else {
            // 사용한다
            dfs(l+1,hap+arr[l+1]); //여기가 잘못, 누적하면 안됨, hap은 이미 누적되어 있는 값임
            dfs(l+1,hap);// 사용안한다
        }
    }


    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        n=scan.nextInt();
        sum=0;
        arr=new int [n+1];
        for (int i=1;i<=n;i++) {
            int k=scan.nextInt();
            sum+=k;
            arr[i]=k;
        }
//        System.out.println(sum);

        // 절반으로 나눈값으로 같아지면 됨
        // 16으로 맞추면 됨

        합이같은부분집합 test=new 합이같은부분집합();
        test.dfs(0,0);
        System.out.println(answer);


//        ArrayList<Integer> arrayList=new ArrayList<>();


    }
}

質問です。

注意事項

コード#コード#

package inflearn.section8_dfs_bfs활용;
import java.util.*;
public class 바둑이승차 {

    static int sum;
    static int arr[];
    static int total;
    static int n;

    public void dfs(int l, int hap) {
        if (hap>total) return; // 이 조건을 추가해야지 빨라짐
        if (l==n) {
            if (hap<=total) {
                if (hap>sum) {
                    sum=hap;
                }
            }
        }
        else {
            // 바둑이를 태운다
            dfs(l+1,hap+arr[l+1]);
            // 바둑이를 태우지 않는다.
            dfs(l+1,hap);

        }
    }

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        total=scan.nextInt();
        n=scan.nextInt();

        arr=new int[n+1];

        for (int i=1;i<=n;i++) {
            arr[i]=scan.nextInt();
        }

        바둑이승차 m1=new 바둑이승차();

        m1.dfs(0,0);
        System.out.println(sum);

    }

}

に質問

解決策

コード#コード#

package inflearn.section8_dfs_bfs활용;
import java.util.*;
public class 최대점수구하기 {

    static int score[];
    static int time[];
    static int n;
    static int m;
    static int hap;

    void dfs(int l, int ts, int tt) {

        if (tt>m) {
            return;
        }
        if (l==n) {
            hap=Math.max(ts,hap);
        }
        else {
            // 문제 푼다
            dfs(l+1,ts+score[l+1],tt+time[l+1]);
            // 문제 안푼다.
            dfs(l+1,ts,tt);
        }
    }


    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        m=scan.nextInt();
        score=new int[n+1];
        time=new int[n+1];

        for (int i=1;i<=n;i++) {
            int sc=scan.nextInt();
            int tt=scan.nextInt();
            score[i]=sc;
            time[i]=tt;
        }
        최대점수구하기 m1=new 최대점수구하기();
        m1.dfs(0,0,0);
        System.out.println(hap);

    }
}

に質問DFSによる重複シーケンスの取得

解決策

コード#コード#

package inflearn.section8_dfs_bfs활용;
import java.util.*;
public class 중복순열구하기 {
    static int arr[];
    static int n;
    static int m;

    public void dfs(int l) {
        // 종료
        if (l==m) {
            String temp="";
            for (int i=0;i<m;i++) {
                temp+=arr[i]+" ";
            }
            System.out.println(temp);
        }
        else {
            for (int i=1;i<=n;i++) {
                arr[l]=i;
                dfs(l+1);
            }
        }

    }

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);

        n=scan.nextInt();
        m= scan.nextInt();
        arr=new int[m];
        중복순열구하기 m1=new 중복순열구하기();
        m1.dfs(0);

    }
}

に質問銅貨を両替する

解決策

コード#コード#

package inflearn.section8_dfs_bfs활용;
import java.util.*;

public class 동전교환 {

    static int n;
    static Integer arr[];
    static int change;
    static int count=Integer.MAX_VALUE;

    public void dfs(int l, int hap) {
        // time Limit이 일어남 -> 가지치기 해서 시간을 줄일수있는 방법을 생각해보자
        // 이 조건도 넣을수 있지 않을까? 이미 앞에서 l이 나왔는데 더 들어갈 필요가 없으면 종료
        // 가지치기해야 할 것을 생각해본다.

        if (count<l) {
            return;
        }
        // 더 줄일수 있지 않을까?!


        if (hap>change)  {
            return;
        }
        else if(hap==change) {
            count=Math.min(count,l);


        }
        else {
            for (int i=0;i<n;i++) {
                dfs(l+1,hap+arr[i]);
            }

        }
    }

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        arr=new Integer[n];
        for (int i=0;i<n;i++) {
            arr[i]=scan.nextInt();
        }
        change=scan.nextInt();

        // 내림차순 정렬
        // 배열은 내림차순 하려면 Integer로 변경해야 한다.
        //
        Arrays.sort(arr,Collections.reverseOrder());

        동전교환 m1=new 동전교환();
        m1.dfs(0,0);
        System.out.println(count);

    }

}