DFS 문제풀이 : 중복순열 다루기, 거스름돈 계산하기

이번에는 중복순열을 Java 코드로 만들어보고, 관련 문제를 풀어볼 것입니다.

사실 저는 고딩때 순열, 조합 이런 것들을 정말 정말 싫어했었는데... 고등학교 졸업 후 약 10년 만에 이런 문제들을 다시 봤지만, 사람은 변하지 않나 봅니다. 여전히 싫네요ㅠ

 

1. 중복순열 다루기

※ 설명

1부터 N 까지 적힌 구슬에서 중복을 허락하여 M번 뽑아서 나열하라

※ 입력

첫 번째 줄에 자연수 N(3<=N<=10) 과 M(2<=M<=N) 이 주어진다

※ 출력

첫 번째 줄에 결과를 출력한다.

출력 순서는 오름차순으로 출력한다.

 

- 중복 순열 다루기

중복순열에서 중요한 것은 함수가 불러와 질 때마다 for 문이 다시 처음부터 돌기 시작한다는 것

1. dfs(0) 이 들어옴 => for 문 시작 pm[0] = 1; && dfs(index+1) == dfs(1)
2. dfs(1) 이 시작됨 => for 문 시작, i=1 일 때 pm [1] = 1 && dfs(index+1) == dfs(2)
3. dfs(2)는 곧 index == 2 임을 의미하고, m = 2 때문에 index == m 이 성립된다. 따라서 함수가 종료되고 pm 배열의 값을 출력한다.
4. 다시 2번으로 돌아간다 이때 index = 1 임으로 pm [1]이고 for문에 따라서 i=2 가 된다. 즉 pm[1] = 2 가 된다. ====> 이후 dfs(index+1) == dfs(2)
5. dfs(2)는 곧 index == 2 임을 의미하고, m = 2 때문에 index == m 이 성립된다. 따라서 함수가 종료되고 pm 배열의 값을 출력한다.

package DFS;

import java.util.Scanner;

public class Permutation_with_repetition {
    // 중복 순열 구하기 : 1부터 N 까지 적힌 구슬에서 중복을 허락하여 M번 뽑아서 나열하기

    // 중복순열에서 중요한 것은 함수가 불러와 질 때 마다 for 문이 다시 처음부터 돌기 시작한다는 것
    // 1. dfs(0) 이 들어옴 => for 문 시작 pm[0] = 1; && dfs(index+1) == dfs(1)
    // 2. dfs(1) 이 시작됨 => for 문 시작, i=1 일 때 pm[1] = 1 && dfs(index+1) == dfs(2)
    // 3. dfs(2) 는 곧 index == 2 임을 의미하고, m = 2 때문에 index == m 이 성립된다.
    // 따라서 함수가 종료되고 pm 배열의 값을 출력한다.
    // 4. 다시 2번으로 돌아간다 이때 index = 1 임으로 pm[1] 이고 for문에 따라서 i=2 가 된다.
    // 즉 pm[1] = 2 가 된다. ====> 이후 dfs(index+1) == dfs(2)
    // 5. dfs(2) 는 곧 index == 2 임을 의미하고, m = 2 때문에 index == m 이 성립된다.
    // 따라서 함수가 종료되고 pm 배열의 값을 출력한다\

    // 이하 반복!!!!

    static int[] pm; // 내까 봅은 값들이 들어있는 배열
    static int n, m = 0; // 각각 전체 구슬의 갯수, 내가 뽑을 횟수

    // dfs 가 받는 int 값은 pm 배열의 index 값
    public static void dfs(int index){
        // m = 2 가 되면 종료 후 배열 값 출력
        if(index == m){
            for(int x : pm)
            {
                System.out.print(x+" ");
            }
            System.out.println();

        }else{
            // for 문에 따라서 i 값이 증가할때마다 dfs 함수가 1번 불러와짐
            // 그리고 다시 for 문이 돌기 시작
            for(int i = 1; i <= n; i++){
                pm[index] = i;
                dfs(index+1);
            }
        }
    }

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

        System.out.print("전체 n 개의 숫자 : ");
        n = scan.nextInt();

        System.out.print("배열의 크기 m : ");
        m = scan.nextInt();

        pm = new int[m];

        dfs(0);
    }
}

 

2. 거스름돈 계산하기

※ 설명

다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름돈을 가장 적은 수의 동전으로 교환해주기 위해서는 최소 몇 번을 주면 될까?

단, 각 단위의 동전은 무한정 쓸 수 있다.

※ 입력

첫 번째 줄에는 동전의 종류개수 N(1 <=N <=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그다음 줄에 거슬러 줄 금액 M(1 <=M <=500)이 주어진다.

단, 각 동전의 종류는 100원을 넘지 않는다.

※ 출력

첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

package DFS;

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class DFS_money {
    static int n = 0; // 전체 동전 갯수
    static int total = 0; // n 개의 동전 종류
    static int minCount = Integer.MAX_VALUE; // Int 의 최대값

    static void moneyCount(int sum, int coinCount, Integer[] arr){
        if(coinCount > minCount) return; // 만약 minCount 보다 coinCount가 더 크다면 return
        if(sum>total)
        {
            // 동전의 합계가 거슬러 줄 금액보다 크다면 - sum 값이 total 보다 크다면 -
            // 계산 필요없음 - return -
            //System.out.println("##### return #####");
            return;
        }

        if(sum == total){ // 거슬러 줄 금액과 동전의 합계가 일치하면 return
            minCount = Math.min(coinCount, minCount); // coinCount 와 minCount 중 최소값 비교
        }
        else
        {
            // 전체 동전 종류 만큼 for 문이 돌기 시작
            // 단 이때 중복순열과 동일하게 재귀함수가 시작될 때마다 다시 for 문이 시작됨
            // 즉 sum+arr[0], coinCount+1, arr 후 다시 moneyCount 함수가 실행된 후
            // 다시 i = 0 , sum+arr[0] 이 시작됨
            // 이렇게 반복하다가 sum 값이 total 과 동일해지거나 total 보다 커지면 return 됨
            for (int i = 0; i < n; i++) {
                //System.out.println("i번째 값 : "+arr[i]);
                //System.out.println("sum : "+sum);
                //System.out.println("coinCount : "+coinCount);

                moneyCount( sum + arr[i], coinCount + 1, arr);
            }
            //System.out.println("###################");
        }
    }

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

        n = scan.nextInt();

        Integer[] arr = new Integer[n];

        for(int i = 0; i < n; i++){
            arr[i] = scan.nextInt();
        }
        // 큰 금액 부터 문제에 적용하기 위해서 arr 를 sort 함
        // 이때 사용하는 것이 Arrays 의 sort 메소드이며, Collections.reverseOrder() 를 사용하면
        // 내림차순으로 DESC 정렬 가능
        // 단, Collections.reverseOrder() 를 사용하기 위해서는 Integer 형 배열[] 이 필요함
        Arrays.sort(arr, Collections.reverseOrder());

        total = scan.nextInt();

        moneyCount(0,0,arr);

        System.out.println(minCount);

    }
}