[DP] 백준 1495번 기타리스트 - JAVA

 

수학적인 공식이 아닌 논리 공식을 이끄는 dp는 어렵다 ㅎㅎ

오늘의 오답노트는 바로 기타리스트~

 

 

---

1. 출처

---

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

1495번: 기타리스트

 

• 공연의 새로운 파트가 시작되기 전 볼륨을 바꿀 수 있음
• 파트의 수, 가장 먼저 실행되는 볼륨, 올릴 수 있는 최대 볼륨 3가지가 주어짐
• 볼륨은 0에서 최대 볼륨 사이로 실행시킬 수 있음
• 이 때, 가장 마지막 파트에서 틀 수 있는 가장 큰 볼륨을 구하는 문제

 

 

---

2. 설계

---

 

 

2-1) BFS가 안되는 이유

처음에는 dp 방법이 연상되기는 했으나

2초라는 시간대와 이 볼륨을 채택하냐 안하냐에 따라 늘어나는 가정들을 보고 BFS로도 구현할 수 있겠다라고 가볍게 생각했다.

즉, 시간복잡도를 제대로 계산하지 않았던 것이다.

 

큐를 이용한 BFS로 구성하게 된다면, 메모리 초과를 마주하게 될 것이다.

그 이유는 1개 가정에서 2개 가정으로, 2개 가정에서 4개 가정으로 ... 기하급수적으로 증가하는 가정의 수 때문이다.

 

그리하여 dp를 생각하여 공식을 끌어내야 하는데, 아무리봐도 공식이 생각나지 않아 답을 보게 되었다.

 

 

2-2) DP 설계

1) 최대 나올 수 있는 볼륨(M)으로 dp를 만든다.

int[] dp = new int[M+1];

 

 

2) dp를 -1로 채운다.

이유는 dp에 몇 번째로 나올 수 있는 볼륨인지 저장할 것이기 때문이다.

즉, 0번째에 나올 수 있는 음향을 체크하기 위함이다. -1로 셋팅안해주면 전 볼륨이 0번째에 나올 수 있다는 의미가 된다.

Arrays.fill(dp, -1);

 

 

3) 가장 처음에 실행되는 볼륨에 0번째에 나올 수 있는 볼륨이라고 저장해준다.

dp[S] = 0;

 

 

4) 결과값을 초기셋팅 한다.

int result = -1;

 

 

5) 현재 진행되는 공연 파트(n)에 나올 수 있는 볼륨(m)을 구한다.

• dp 배열 전체를 돌려보며 n-1 파트에 나왔던 볼륨을 체크한다.
• n-1 파트에 나왔던 볼륨에서 현재 공연에서 조절할 수 있는 볼륨을 +, - 해준다.
  • 여기서 중요한 점은 dp의 값을 바로 바꾸지 않는 것이다.
  • 만약 dp[2] = 1에서 +2볼륨을 조절할 수 있어서 dp[4] = 1 -> 2로 바꿔주게 된다면, dp[4]에서 2번째 파트 음향이 나올 수 있는 가정을 판단해볼 수 없다.
• 현재 진행되는 공연 파트(n)에서 나올 수 있는 볼륨들(m)을 List에 저장하고, 한 번에 업데이트 해준다.
• 업데이트하면서 현재 공연 파트가 마지막 파트일 경우 볼륨의 최대값을 갱신해준다.

for(int n=1; n<=N; n++){//현재 공연 파트
	List<Integer> change = new ArrayList<>();//현재 공연 파트에서 나올 수 있는 볼륨들 저장
	for(int m=0; m<=M; m++){//0~최대볼륨 탐색, 즉 dp 전체 탐색
		if(dp[m]==n-1){//이전 공연 파트에서 나왔던 볼륨 탐색
            int plus = m+V[n];
            int minus = m-V[n];

            if(plus<=M) change.add(plus);
            if(minus>=0) change.add(minus);
                    
		}
	}

	for(int i=0; i<change.size(); i++){//현재 공연 파트에서 나왔던 볼륨들 전체 반영(업데이트)
		int change_idx = change.get(i);
		dp[change_idx] = n;
		if(n==N) result = Math.max(result, change_idx);//마지막 공연일 경우 max값 갱신
	}
}

 

 

 

---

3. 전체 코드

---

3-1) dp (정답)

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String NSM = br.readLine();
        StringTokenizer st = new StringTokenizer(NSM, " ");
        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        String Vs = br.readLine();
        st = new StringTokenizer(Vs, " ");
        int[] V = new int[N+1];
        for(int i=1; i<=N; i++){
            V[i] = Integer.parseInt(st.nextToken());
        }

        //입력 끝

        int[] dp = new int[M+1];
        Arrays.fill(dp, -1);
        dp[S] = 0;
        int result = -1;

        for(int n=1; n<=N; n++){
            List<Integer> change = new ArrayList<>();
            for(int m=0; m<=M; m++){
                if(dp[m]==n-1){
                    int plus = m+V[n];
                    int minus = m-V[n];

                    if(plus<=M) change.add(plus);
                    if(minus>=0) change.add(minus);
                    
                }
            }

            for(int i=0; i<change.size(); i++){
                int change_idx = change.get(i);
                dp[change_idx] = n;
                if(n==N) result = Math.max(result, change_idx);
            }
        }
        System.out.println(result);
    }
}

 

 

3-2) BFS (오답)

import java.util.*;
import java.io.*;

class Main {

    static int N;
    static int S;
    static int M;
    static int[] V;
    static int result = -1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String NSM = br.readLine();
        StringTokenizer st = new StringTokenizer(NSM, " ");
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        BFS();

        System.out.println(result);
    }

    public static void BFS(){
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(S,-1));

        while(!q.isEmpty()){
            Node cur = q.poll();

            if(cur.order == N-1){
                result = Math.max(cur.num, result);
                continue;
            }
            
            int nextP = cur.num+V[cur.order+1];
            int nextM = cur.num-V[cur.order+1];

            if(nextP<=M) q.offer(new Node(nextP, cur.order+1));
            if(nextM>=0) q.offer(new Node(nextM, cur.order+1));
        }
    }

    public static class Node{
        int num;
        int order;

        public Node(int num, int order){
            this.num = num;
            this.order = order;
        }
    }
}