방 번호

• 문제 링크

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

• 내가 푼 방법

max() 메서드에 대해서 먼저 설명드리면

max() 메서드는 들어온 두개의 String 의 대소비교를 하는 부분입니다.

아무래도 수가 엄청나게 커질 수 밖에 없는 문제이기 때문에 (최대 50자) String 으로 풀어야하고, 대소 비교를 하기 위해서도 String 으로 할 수 있지만, BigInteger 를 사용할 수 있습니다.

BigInteger 를 사용하게 되면 굉장히 빠르게 대소 비교를 할 수 있습니다.

일단, max() 메서드에 대해서 설명드리면 a 가 빈 문자열이라면 ? 바로 b 를 반환해줍니다.

볼 필요도 없으니까요

만일 a.length == b.length 라면 실제 숫자로 비교해봐야 합니다.

이 때, BigInteger 를 사용해볼 수 있죠

만일 서로의 자릿수가 다르다면 자릿수가 더 높은 수를 반환할 수 있습니다.

예를 들어

10010 과 1001 중 더 큰 수는 10010 이죠

근데, 이것마저도 BigInteger 로 대소비교를 하게 되면 문제가 발생합니다.

00010 1001 중 실제로 더 큰 숫자는 00010 입니다.

왜냐하면 이 수로만 이루어진 것이 아니라, 어떤 숫자의 뒤에 붙을 수이기 떄문입니다.

이러한 예외가 있기 때문에 서로의 자릿수가 다를 때에는 자릿수로 비교를 해주어야합니다.

이제 dp 부분입니다.

dp 의 정의는 이것입니다.

dp[i] = 돈이 i 남았을 때 만들 수 있는 최대 수

이렇게 가정해놓고 순서대로 코드를 살펴봅시다.

dfs 를 호출하는 부의 코드는 아래와 같습니다.

String answer = "0";

for (int i = 1; i < N; i++) {
	if (0 <= M - cost[i]) {
		answer = max(answer, i + dfs(M - cost[i]));
	}
}

일단 기본적으로 0으로 시작하는 것은 불가능 하기에 초기 답을 0으로 설정해놓고, 시작하는 수를 1 부터 N - 1 까지 실행시켜주어 0으로 시작하는 경우의 수를 제외하는 것입니다.

이렇게 하게 되면 dfs 의 로직을 굉장히 단순화 할 수 있습니다.

dfs 의 코드는 아래와 같습니다.

public static String dfs(int money) {
	if (money == 0) {
		return "";
	}

	if (dp[money] != null) {
		return dp[money];
	}

	dp[money] = "";

	for (int i = 0; i < N; i++) {
		if (0 <= money - cost[i]) {
			dp[money] = max(dp[money], i + dfs(money - cost[i]));
		}
	}

	return dp[money];
}

money == 0 이 될 때, 성공한 경우이니 빈 문자열을 반환해줍니다.

그리고 dp[money] 가 null 이 아니라면 이미 구해본 경우의 수이기 때문에 이 경우에도 결과를 반환해줍니다.

그리고서 dp[money] 에 공백을 넣어주고 for 문으로 돌면서 0 부터 N - 1 까지의 숫자를 덧붙여주면서 최대값을 계속 갱신해나갑니다.

그리고 구한 최대값을 그대로 반환하면 이 문제는 끝입니다.

• 시간 복잡도

O(M * M * M)

• Code

import java.math.BigInteger;
import java.util.*;
import java.io.*;

// 1082 : 방 번호

public class Main {

    public static int N;
    public static int M;
    public static String[] dp;
    public static int[] cost;

    public static String max(String a, String b) {
        if (a.equals("")) {
            return b;
        }

        if (a.length() == b.length()) {
            BigInteger ab = new BigInteger(a);
            BigInteger bb = new BigInteger(b);

            return ab.max(bb).toString();
        }

        return a.length() > b.length() ? a : b;
    }

    public static String dfs(int money) {
        if (money == 0) {
            return "";
        }

        if (dp[money] != null) {
            return dp[money];
        }

        dp[money] = "";

        for (int i = 0; i < N; i++) {
            if (0 <= money - cost[i]) {
                dp[money] = max(dp[money], i + dfs(money - cost[i]));
            }
        }

        return dp[money];
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("/Users/jaeyeonkim/Desktop/CodingTest/CodingTest/BJ/Java/_1082_problem/src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        cost = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cost[i] = Integer.parseInt(st.nextToken());
        }

        M = Integer.parseInt(br.readLine());
        dp = new String[M + 1];

        String answer = "0";

        for (int i = 1; i < N; i++) {
            if (0 <= M - cost[i]) {
                answer = max(answer, i + dfs(M - cost[i]));
            }
        }

        System.out.println(answer);
    }

}