[BOJ18511] 큰 수 구성하기

백준 18511 큰 수 구성하기

https://www.acmicpc.net/problem/18511

18511번: 큰 수 구성하기

문제

N보다 작거나 같은 자연수 중에서, 집합 K의 원소로만 구성된 가장 큰 수를 출력하는 프로그램을 작성하시오. K의 모든 원소는 1부터 9까지의 자연수로만 구성된다.

예를 들어 N=657이고, K={1, 5, 7}일 때 답은 577이다.

입력

첫째 줄에 N, K의 원소의 개수가 공백을 기준으로 구분되어 자연수로 주어진다. (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3) 둘째 줄에 K의 원소들이 공백을 기준으로 구분되어 주어진다. 각 원소는 1부터 9까지의 자연수다.

단, 항상 K의 원소로만 구성된 N보다 작거나 같은 자연수를 만들 수 있는 경우만 입력으로 주어진다.

 

 

하노이 탑에서 언급한 것 처럼

1. 종료 조건
2. 규칙

두가지에 집중해보았다.

우선 종료 조건은 문제에서 모두 주어져 있기 때문에 (N보다 작거나 같은 자연수 중 가장 큰 수) 굳이 따로 생각할 필요는 없다.

 "N < 구하는 수"로 두면 되겠다.

 

규칙은 하노이 탑처럼 깨끗한(?) 규칙이 나오진 않는다.

하지만 조금만 생각해보면 브루트포스인 것을 쉽게 알 수 있고, 전체 탐색을 위해 K배열을 정렬해줬다.

이제 해야할 일은 전체 탐색을 하는 것 뿐이다.

사실 이 때 for문 내에서 1 -> 15 -> 157 -> 5 -> 517 -> 571 -> 이런식으로 하려고 했는데 문제를 다시 읽어보니 숫자가 두번 쓰일수도 있고, 이 방법은 그냥.. 말이 안된다.ㅎ 잘못된 방식이라는 걸 깨닫고 바로 싹-다 지워버렸다.

 

그럼 어떻게 하느냐? 그 식 ((now * 10) + K[i])을 바로 findBig함수에 전달하면 된다. 

어차피 종료 구문에 걸려 그 전 함수 위치로 돌아갈테니까.

 

그렇게 해서 바로 성공!

정답 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ18511 {
    private static int N, num, res, cnt = 0, now = 0;
    private static int[] K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        num = Integer.parseInt(st.nextToken());
        K = new int[num];

        st = new StringTokenizer(br.readLine()," ");
        for(int i = 0; i < num; i++) {
            K[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(K);
        findBig(0);
        System.out.println(res);
    }

    private static void findBig(int now){
        if(N < now) return;
        if(res < now) res = now;

        for(int i = 0; i < num; i++){
            findBig((now * 10) + K[i]);
        }
    }
}