필요한 장난감의 최소 개수 구하기 문제 풀이 (너비 우선 탐색 이용, BFS)

출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략

 

난이도

상

 

 

 

문제

어린이집을 경영하는 원석이는 어린이날을 맞아 어린이집에 다니는 n명의 아이들에게 장난감을 나눠 주기로 마음 먹었습니다.
모든 아이들에게 같은 수의 장난감을 주려고 했지만, 그중 m(0<=m<=n)명의 욕심쟁이 어린이들은 모두 같은 개수의 장난감을 받으면 삐져버립니다.
따라서 이 욕심쟁이 어린이들에게는 남들보다 장난감을 하나씩 더 주기로 했습니다.
종교적인 이유로 인해, 아이들에게 나누어 주는 장난감의 총 수 c는 십진수로 썼을 때 특정 숫자만으로 구성 되어야 합니다.
예를 들어 특정 수가 1과 2라고 하면 n이 5이고 m이 2일때 12개, 112개, 1112개 ... 의 장난감이 필요합니다.
예산이 빠듯한 관계로 장난감을 가능한 적게 사려고 합니다.(12개)
위와 같은 조건을 만족하는 최소의 c를 계산하는 프로그램을 작성하세요.
단, 모든 어린이가 장난감을 하나씩은 받아야 합니다.

 

시간 및 메모리 제한

프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 합니다.

 

 

입력

입력의 첫 줄에는 테스트 케이스의 수 t (t<=50) 가 주어집니다. 
각 테스트 케이스는 c에 사용할 수 있는 자릿수의 목록 d와 n, m (0<=m<n<=10000) 으로 주어집니다.
자릿수 목록은 최소 한개의 숫자는 포함하며, 자릿 수 목록에 한 숫자가 2번 주어지는 일은 없습니다.

 

출력

각 테스트 케이스마다 필요한 최소 장난감의 수를 출력합니다.
만약 모든 조건을 만족하는 장난감의 개수를 찾을 수 없을 경우, IMPOSSIBLE을 출력합니다.

 

예제입력

5
1 7 0
1 10 1
0 7 3
345 9997 333
35 9 8

 

예제 출력

111111
11
IMPOSSIBLE
35355353545
35

 

 

풀이

 

들어가기 앞서, 제가 푼 문제의 정답은 위 예제 출력의 결과와 다르게 나왔음을 알려드립니다.

해당 결과는 입력 345 9997 333 에 관한 것이며, 예제 출력의 결과인 35355353545 보다 작은 수가 나왔습니다.

그런데, 직접 계산기로 계산을 해보니, 정답이 맞습니다. 그래서 수정 없이 올립니다.

 

만약 제 풀이가 틀렸다면, 말씀해주시면 감사하겠습니다.

 

저는 아래와 같은 방법으로 풀었습니다.

 

 

필요한 사탕의 수를 x라고 했을 때 최소 개수 F(x)는

F(x) = n * x + m 을 만족할 것 ( n 명 중 m 명에게만 1개씩 더 )



너비 우선 탐색으로 조합된 숫자로 이루어진 값을 a 라고 했을 때

a % F(x) = 0 인지 확인하는 문제라고 판단



이때, F(x) < "전체 사탕의 개수" 를 만족해야 한다.



깊이 우선 탐색이 아닌, 너비 우선 탐색으로 숫자를 조합해보아야 하는 이유는,

"최소값"을 찾아야 하기 때문이다.

 

package BFS;

import java.util.*;

public class three {

    // 탐색 시작
    static long search(long[] num, long n, long m) {
        // 탐색된 수가 들어갈 공간
        Map<Long, Long> searched = new TreeMap<>();
        // 탐색할 수가 들어갈 공간
        Queue<Long> candidate = new LinkedList<>();

        /* num을 먼저 정렬하도록 한다. */
        Arrays.sort(num);

        // 초기화
        for (int i=0; i<num.length; i++) {
            // 트리 맵에 1자리 숫자로 이루어진 수를 넣는다.
            searched.put(num[i], (long)0);
            candidate.add(num[i]);
        }


        while(!candidate.isEmpty()) {
            // 탐색할 대상이 되는 장난감 개수
            long here = candidate.poll();
            // 탐색한 회수 => 이 문제 풀이에서는 의미없는 값입니다.
            long cost = searched.get(here);

            for (long x=1, smallest = 0; smallest < here; x++) {
                // 조건을 만족하는 장난감 개수
                smallest = n*x+m;

                // 조건에 맞는 숫자를 찾으면 멈춘다.
                if (here % smallest == 0) {
                    return here;
                }
            }


            // 배열을 돌려가면서 하나씩 뒤에 숫자를 붙여본다. => 이때 num은 정렬되어 있으므로 작은 숫자 순서로 정렬한다.
            for (int i=0; i<num.length; i++) {
                // 다음 숫자를 뒤에 붙여본다.
                long there = here * 10 + num[i];

                if (!searched.containsKey(there)) {
                    // here 탐색 완료 => there의 깊이 세팅
                    searched.put(there, cost+1);
                    // 탐색할 목록에 there 을 넣는다.
                    candidate.add(there);
                }

            }
        }
        return -1;
    }

    public static void main(String[] args) {
        long[] input1 = {1};
        long[] input2 = {1};
        long[] input3 = {0};
        long[] input4 = {3,4,5};
        long[] input5 = {3,5};

        long result1 = search(input1, 10, 1);
        long result2 = search(input2, 7, 0);
        long result3 = search(input3, 7, 3);
        long result4 = search(input4, 9997, 3333);
        long result5 = search(input5, 9, 8);

        System.out.println(result1);
        System.out.println(result2);
        System.out.println(result3);
        System.out.println(result4);
        System.out.println(result5);
    }
}

 

결과

11
111111
-1
4435343
35

 

여기서 -1은 IMPOSSIBLE 을 의미합니다.