문제 링크
문제
티어: 골드 1
알고리즘: dp
좌우 한 줄로 있는 N개의 장소 각각에 조약돌이 몇 개씩 놓여 있다.
철수가 할 수 있는 작업의 종류는 아래 두 가지이다.
- 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기
- 한 장소에서 임의의 개수의 조약돌을 가져가기
어떤 장소에 조약돌이 더 이상 없는 경우에도 그 장소는 그대로 남아 있어서, 초기에 인접하지 않았던 두 장소가 인접한 것으로 바뀌지 않는다.
철수는 위의 두 작업 중 하나를 골라서 실행하는 것을 반복하여 모든 조약돌을 가져가려고 한다.
초기에 각 장소에 있는 조약돌들의 개수를 입력받아, 철수가 할 수 있는 최소의 작업 횟수를 계산하는 프로그램을 작성하라.
입력
첫 번째 줄에 장소의 개수 N이 주어진다.
두 번째 줄에 N개의 장소 각각에 있는 조약돌 개수가 왼쪽 장소에 해당하는 것부터 순서대로 공백 하나씩을 사이로 두고 주어진다.
출력
첫 번째 줄에 답을 출력한다.
제한
- 2 ≤ N ≤ 2 500
- 각 장소의 초기 조약돌 개수는 1 이상 108 이하이다.
풀이
철수가 두 가지 작업으로 모든 조약돌을 가져올 수 있는 최소한의 작업 횟수를 출력해야 한다.
예제 입력 4번을 보면,
5
2 3 6 10 51 번째 장소에서 모든 조약돌을 가져올 수 있는 경우는 다음과 같은 2가지 존재한다. (앞에서부터 0을 만들어주는 것이 목표다.)
- 그 장소에서만 가져오기
- 인접한 장소와 함께 가져오기
먼저, 내가 풀면서 의문이 들었던 것은 다음과 같다.
조약돌을 가져오는 순서는 상관 없는가?
조약돌을 가져오는 순서는 전혀 상관없다. 왜냐하면 1번 째 장소에서 조약돌을 가져오려면 결국 그 장소와 인접한 장소 이 두 가지 경우말고는 없기 때문이다.
다음 조약돌과 다다음 조약돌의 개수를 맞춰주는 경우도 따져줘야 하는가?
예를 들어 3 2 1일 때 첫 번째 장소를 0으로 만들어 주기 위해서
첫 번째, 두 번째 장소에서 하나를 가져오고, 첫 번째 장소에서 두개를 가져오는 경우 0 1 1이 된다.
그래서 0 0 0으로 만들어주는데 총 횟수는 3회가 된다.
그런데 두 번째와 세 번째를 같게 맞춰주기 위해서 2번 작업이 필요하기 때문에 이러한 경우는 따져주지 않아도 된다.
그래서 현재 장소를 0으로 만들기 위해서는 인접한 장소와 한 번에 또는 현재 장소에서 한 번에 이 두 가지 경우만 고려해주면 되는 것이다.
예를 들어 2 3이라고 했을 때 (A < B)
1. 인접한 장소와 한 번에 -> 0 1
2. 현재 장소에서 한 번에 -> 0 3
만약 3 2라면 어떻게 해야될까? (A > B)
1. 현재 장소에서 한 번에 -> 0 2
이 경우만 따져주면 된다.
왜냐하면 2번 경우로 0을 만들어주기 위해서 2번의 작업 횟수가 필요하기 때문이다.
만약 3 3 같다면 (A == B)
1. 인접한 장소와 한 번에 -> 0 0
항상 이 경우가 최선이다.
위 풀이의 시간 복잡도를 계산해 보면,
첫 번째에서는 2가지
두 번째에서는 3가지
세 번재에서는 4가지
...
이렇게 N 번째까지 반복된다.
그래서 시간 복잡도는 1 ~ N까지의 합이며 시간 초과없이 여유롭게 통과할 수 있는 시간이다.
O(N * (N + 1) / 2) -> O(N^2)
그런데 고민했던 것은 이를 구현하기 위해 2차원 dp를 생각했는데, 조약돌의 개수가 최대 10^8이기 때문에 배열로 표현하는 것이 불가능했다. 그래서 이 방법이 정해인지는 모르겠지만, HashMap을 이용해서 현재 상태에 경우의 수를 유지해줬다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
HashMap<Integer, Integer> map = new HashMap<>();
map.put(arr[0], 0);
for(int i=0; i<N - 1; i++) {
HashMap<Integer, Integer> nextMap = new HashMap<>();
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
int A = entry.getKey();
int v = entry.getValue();
int B = arr[i + 1];
if(A == 0) {
update(B, v, nextMap);
} else {
if(A < B) {
update(B - A, v + 1, nextMap);
update(B, v + 1, nextMap);
} else if(A > B) {
update(B, v + 1, nextMap);
} else {
update(0, v + 1, nextMap);
}
}
}
map = nextMap;
}
int answer = Integer.MAX_VALUE;
for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
int num = entry.getKey();
int value = num == 0 ? entry.getValue() : entry.getValue() + 1;
answer = Math.min(answer, value);
}
System.out.println(answer);
}
static void update(int num, int cnt, HashMap<Integer, Integer> map) {
if(map.get(num) == null) {
map.put(num, cnt);
} else {
map.put(num, Math.min(map.get(num), cnt));
}
}
}