백준13902_개업2

문제

개업2

접근 방법

먼저, 한 손이나 두 손을 사용해서 짜장면을 만들 수 있는 그릇의 경우(numbers)를 조합을 이용하여 구한다. 그리고 해당 경우들은 한 번에 처리할 수 있는 경우이기 때문에 1로 초기화해준다. 나는 만들 수 있는 그릇의 수를 LinkedList 자료구조를 사용했다. 이유는 add 하는 경우가 O(N^2) 이기 때문에 해당 시간을 줄여야겠다고 생각했다.

List<Integer> numbers = new LinkedList<>();
for (int i = 0; i < M; i++) {
    wok[i] = stoi(st.nextToken());
    if (!numbers.contains(wok[i])) {
        numbers.add(wok[i]);
        dp[wok[i]] = 1;
    }
}
Arrays.sort(wok);
for (int i = 0; i < M; i++) {
    for (int j = i + 1; j < M; j++) {
        if (wok[i] + wok[j] > N) {
            break;
        }
        if (!numbers.contains(wok[i] + wok[j])) {
            numbers.add(wok[i] + wok[j]);
            dp[wok[i] + wok[j]] = 1;
        }
    }
}

만들 수 있는 그릇 수(numbers)를 이용해서 1부터 N그릇 수를 만드는 데 걸리는 최소값은 구한다. 예를들어 i 그릇 수를 만드는 데 걸리는 최소값을 구한다고 할 때, numbers를 하나씩 꺼내서 만들 수 있는지 확인한다. (i - number) 값이 0보다 크면 해당 웍으로 이전에 만든 적이 있다는 것이고, 해당 값에서 + 1을 한 값과 기존의 값을 비교하여 현재 그릇 수를 만들 때까지 걸린 최소값을 구한다.

for (int i = 1; i <= N; i++) {
    if (dp[i] == 1) {
        continue;
    }
    for (Integer number : numbers) {
        if (i - number > 0) {
            dp[i] = Math.min(dp[i], dp[i - number] + 1);
        }
    }
}

제출 결과

“시간 초과”

왜 이러한 결과가 나왔을까?

이유는 LinkedList 으로 만든 numbers 가 문제였다. 정확하게는 중복된 값을 제거하기 위해서 contains() 메소드를 2번이나 사용하고 있는데 이 부분에서 시간 초과가 발생하는 것이다. List의 경우 contains() 메소드를 실행할 때 O(N)의 시간 복잡도를 가지고 있다. 그런데 위의 코드에서 2중 for문 안에 contains() 메소드가 있고 따라서, 해당 경우에는 O(M * M * N) 의 시간 복잡도를 가지기 때문이다.

해결 방법 및 배운 점

이를 해결하기 위해서 Set 자료구조로 변경하여 해결할 수 있었다.

Set의 경우 add, contains 모두 O(1)의 시간 복잡도를 가진다. 따라서 해당 문제처럼 List, Set 모두 사용 가능하고 탐색을 많이 해야하는 경우 Set을 사용하는 것이 더 적합다는 것을 알 수 있었다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	private static final int MAX = 987654321;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = stoi(st.nextToken());
		int M = stoi(st.nextToken());
		st = new StringTokenizer(br.readLine());
		int[] wok = new int[M];
		Set<Integer> numbers = new HashSet<>();
		int[] dp = new int[N + 1];
		Arrays.fill(dp, MAX);
		for (int i = 0; i < M; i++) {
			wok[i] = stoi(st.nextToken());
			if (!numbers.contains(wok[i])) {
				numbers.add(wok[i]);
				dp[wok[i]] = 1;
			}
		}
		Arrays.sort(wok);
		for (int i = 0; i < M; i++) {
			for (int j = i + 1; j < M; j++) {
				if (wok[i] + wok[j] > N) {
					break;
				}
				if (!numbers.contains(wok[i] + wok[j])) {
					numbers.add(wok[i] + wok[j]);
					dp[wok[i] + wok[j]] = 1;
				}
			}
		}
		for (int i = 1; i <= N; i++) {
			if (dp[i] == 1) {
				continue;
			}
			for (Integer number : numbers) {
				if (i - number > 0) {
					dp[i] = Math.min(dp[i], dp[i - number] + 1);
				}
			}
		}
		System.out.println(dp[N] == MAX ? -1 : dp[N]);
	}

	private static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

Written by@슬로
느리지만 꾸준하게 나아갑니다.