문제 설명
이번 문제는 마지막 곡의 최대 볼륨을 구하는 문제로,
1. i번째를 연주하려면, 이전의 볼륨에서 정해진 변경 볼륨대로 + or -를 해야한다.
2. 볼륨이 0 <= volume <= M 을 충족해야 한다.
3. 모든 곡을 리스트에 적힌 순서대로 연주해야 한다.
1. DFS
가장 먼저 DFS를 통해 최대값을 도출하려 했습니다.
import java.util.*;
import java.io.*;
public class Main {
static int answer = -1;
public static void main(String[] args) throws Exception {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st =
new StringTokenizer(br.readLine());
int seq = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
int limit = Integer.parseInt(st.nextToken());
int[] arr = new int[seq];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < seq; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
dfs(arr, start, limit, 0, seq);
System.out.println(answer);
}
public static void dfs(int[] arr, int start, int limit, int idx, int seq) {
if(idx == seq) {
answer = Math.max(answer, start);
return;
}
if(start - arr[idx] >= 0) {
dfs(arr, start - arr[idx], limit, idx + 1, seq);
}
if(start + arr[idx] <= limit) {
dfs(arr, start + arr[idx], limit, idx + 1, seq);
}
}
}그리고 당연하게도... 시간초과가 발생했습니다.
이유는 바로 상태저장 없이 DFS를 진행했기 때문입니다.
아래 그림을 통해 더 자세히 설명하자면
- 초기 상태에서 1번째 연주를 진행하면서 볼륨 증감 시도 (1 * 2)
-> 2^1 - 1번째 연주 끝난 상태에서 2번째 연주를 진행하면서 볼륨 증감 시도 (2 * 2)
-> 2^2 - 2번째 연주 끝난 상태에서 3번째 연주를 진행하면서 볼륨 증감 시도 (4 * 2)
-> 2^3 - 마지막으로 N - 1번째 연주 끝난 상태에서 N번째 연주를 진행하면서 볼륨 증감 시도 (2^N-1 * 2)
-> 2^N
💡 무조건 증감을 시도하기 때문에, 항상 O(2^N)의 시간 복잡도가 생기면서 시간초과 발생
2. DFS + visited배열
이에, 중복되는 상황을 제거하기 위해, 2차원 boolean배열을 통해 중복되는 접근을 차단했습니다.
import java.util.*;
import java.io.*;
public class Main {
static int answer = -1;
public static void main(String[] args) throws Exception {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st =
new StringTokenizer(br.readLine());
int seq = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
int limit = Integer.parseInt(st.nextToken());
boolean[][] v = new boolean[seq + 1][limit + 1];
int[] arr = new int[seq];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < seq; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
dfs(arr, start, limit, 0, seq, v);
System.out.println(answer);
}
public static void dfs(int[] arr, int start, int limit, int idx, int seq, boolean[][] v) {
if(idx == seq) {
answer = Math.max(answer, start);
return;
}
if(start - arr[idx] >= 0 && !v[idx + 1][start - arr[idx]]) {
v[idx + 1][start - arr[idx]] = true;
dfs(arr, start - arr[idx], limit, idx + 1, seq, v);
}
if(start + arr[idx] <= limit && !v[idx + 1][start + arr[idx]]) {
v[idx + 1][start + arr[idx]] = true;
dfs(arr, start + arr[idx], limit, idx + 1, seq, v);
}
}
}그리고 결과는... 정답이 였습니다.
아래의 그림으로 성공하는 이유를 설명하자면,
💡 이전에는 중복이 가능했지만, 2차원 배열을 통해 이미 방문한 곳을 차단했기 때문에 중복 없이 탐색이 가능!
-> 시간복잡도가 O(N * (M + 1)) 로 대폭감소 / N = 곡 수, M = 최대 볼륨
3. DP (2차원 배열)
정답 후 다른 사람들의 정답을 찾아 파악해봤는데, 대부분 DP를 통해 문제해결을 도모. 차이점 비교를 위해서 코드를 작성해봤습니다.
import java.util.*;
import java.io.*;
public class Main {
static int answer = -1;
public static void main(String[] args) throws Exception {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st =
new StringTokenizer(br.readLine());
int seq = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
int limit = Integer.parseInt(st.nextToken());
int[] arr = new int[seq];
boolean[][] dp = new boolean[seq + 1][limit + 1];
dp[0][start] = true;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < seq; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < seq; i++) {
for(int j = 0; j < limit + 1; j++) {
if(dp[i][j]) {
if(j + arr[i] <= limit) {
dp[i + 1][j + arr[i]] = true;
}
if(j - arr[i] >= 0) {
dp[i + 1][j - arr[i]] = true;
}
}
}
}
int answer = -1;
for(int j = limit; j >= 0; j--) {
if(dp[seq][j]) {
answer = j;
break;
}
}
System.out.println(answer);
}
}
DP를 풀면서 이전의 DFS + 2차원 배열 코드와 다른 점으로는
- DFS + 2차원 배열
- 방문 처리를 통한 중복 방지
- 재귀를 통한 다음 index로 이동
- 끝까지 이동한 후, 최대 볼륨을 일일히 비교
- DP
- 가능한 모든 경우를 boolean 2차월 배열로 초기 세팅
- 시작 위치 true
- true인 곳을 다음 볼륨 비교 후 true로 업데이트
- 모든 방문 후, 최대 index를 파악 후 return
였습니다.
4. DP (1차원 배열)
더 나아가, 1차원 배열로도 진행이 가능합니다.
import java.util.*;
import java.io.*;
public class Main {
static int answer = -1;
public static void main(String[] args) throws Exception {
BufferedReader br =
new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st =
new StringTokenizer(br.readLine());
int seq = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
int limit = Integer.parseInt(st.nextToken());
int[] arr = new int[seq];
boolean[] preDP = new boolean[limit + 1];
boolean[] nextDP = new boolean[limit + 1];
preDP[start] = true;
st = new StringTokenizer(br.readLine());
for(int i = 0; i < seq; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for(int z = 0; z < seq; z++) {
Arrays.fill(nextDP, false);
for(int i = 0; i < limit + 1; i++) {
if(preDP[i]) {
if(i + arr[z] <= limit) {
nextDP[i + arr[z]] = true;
}
if(i - arr[z] >= 0) {
nextDP[i - arr[z]] = true;
}
}
}
boolean[] temp = nextDP;
nextDP = preDP;
preDP = temp;
}
int answer = -1;
for(int j = limit; j >= 0; j--) {
if(preDP[j]) {
answer = j;
break;
}
}
System.out.println(answer);
}
}
이전의 2차원 배열 DP과 지금의 1차원 배열이 다른 점으로는
- 2차원 배열
- 모든 경우의 수를 세팅
- 모든 작업 후 마지막 곡 index에서 최대 볼륨 index를 find
- 1차원 배열
- 이전 곡의 배열, 다음곡의 배열로 2개의 1차원 배열만 생성
-> 이전 곡에서 볼륨 조절을 진행하기 때문에! - 다음 곡 볼륨 로직 후, 배열 주소 변경
- 이전 곡의 배열, 다음곡의 배열로 2개의 1차원 배열만 생성
💡 이를 통해, 공간 복잡도를 O(N * M) → O(2M)로 줄일 수 있게 됩니다!
느낀 점
- 해당 문제를 풀면서 다양한 접근이 가능하다는 걸 알게 되었습니다.
- 특히, 해당 문제에서 방식에 따른 장점을 파악할 수 있게 되었습니다.
Backend Developer