경우의 수 문제(Brute-Force Search)

1. "모든" 경우에 대하여 탐색하여 결과를 찾음 --> 무식하게 다찾아보기.

2. 문제의 범위가 작은 경우 완전 탐색으로 해를 찾음

3. 수열, 조합과 같은 문제를 푸는데 사용됨.

4. 문제 정의

 -  어느 국가에서 10만원, 20만원, 50만원, 100만원, 200만원, 500만원 지폐를 사용.

 -  A는 3000만원 지불 필요.

 - 6가지 지폐를 활용하여 300만원 지불하는 방법은 모두 몇 가지?

 

5. 지폐가 늘어나면 for문이 추가됨. computation time이 지수적으로 증가함. 

 

 6. code

package BruteForceSearch;

public class bruteForceSearch {

    public static void main(String[] args) {

        int[] bills = {10, 20, 50, 100, 200, 500};

        int count = 0;
        int price = 3000;

        for(int i0 = price; i0 >=0; i0-=bills[0]){

            for(int i1=i0; i1>=0; i1-=bills[1]) {

                for (int i2 = i1; i2 >= 0; i2 -= bills[2]) {

                    for (int i3 = i2; i3 >= 0; i3 -= bills[3]) {

                        for (int i4 = i3; i4 >= 0; i4 -= bills[4]) {

                            if (i4 / bills[5] <= 0) {
                                count++;

                            }

                        }

                    }

                }
            }
        }

        System.out.println("지불 방법의 수 :  " + count);

    }

}

*github : https://github.com/bsh6463/Algorithm/tree/main/BruteForceSearch