백준13902_개업2
2022.01.09
문제
접근 방법
먼저, 한 손이나 두 손을 사용해서 짜장면을 만들 수 있는 그릇의 경우(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);
}
}