[BOJ 1495] 기타리스트 (Java, DP)

 

 

 

---

문제 링크 

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

1495번: 기타리스트

---

문제 풀이 

- 시간복잡도의 경우 상향식 O(N), 하향식 O(2^N) 소요됨 

- 하향식의 경우 메모리제이션 기법 사용하여 풀이

- 상향식으로 풀 때 초기항부터 누적하는 형태로 풀이할 경우 최대치가 int를 초과하는 것으로 생각됨 

(최대치 따로 구해보기)

 

*하향식 풀이의 경우 아래 기술 블로그 통해 형식 이해함

https://steady-coding.tistory.com/172

[BOJ] 백준 1495번 : 기타리스트 (JAVA)

 

---

제출 코드 

(1) Bottom-Up

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

public class Main {
    static int N, S, M;

    static int[] VOLUME;

    static long[][] DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 곡 수
        S = Integer.parseInt(st.nextToken()); // 시작 볼륨
        M = Integer.parseInt(st.nextToken()); // 최대 볼류

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

        DP = new long[N + 1][M + 1]; // [곡 순서][볼륨]
    }

    static void executeByBottomUp() {
        DP[0][S] = 1; //[시작][초기볼륨]

        for(int i = 1; i <= N; i++) { // 곡 순서
            for(int v = 0; v <= M; v++) { // 볼륨
                if(DP[i - 1][v] > 0) {
                    int v1 = v + VOLUME[i];
                    int v2 = v - VOLUME[i];

                    if(v1 <= M) DP[i][v1] += DP[i - 1][v];
                    if(v2 >= 0) DP[i][v2] += DP[i - 1][v];
                }
            }
        }

        int result = -1;
        for(int v = 0; v <= M; v++) {
            if(DP[N][v] > 0) {
                result = Math.max(result, v);
            }
        }

        System.out.println(result);
    }
    
    public static void main(String[] args) throws Exception {
        input();
        executeByBottomUp();
    }    
}

 

(2) Top-Down 방식

(주의) DP 배열을 사용할 때 '아직 방문 한 없다'는 의미의 -1 과 '음량 조절할 수 없는 경우'의 -1에 대한 의미가 중복되어서, 중복 연산이 발생했고 이로인해 '틀렸습니다' 출력됨 (아래 글 참고)

 

https://www.acmicpc.net/board/view/2481

글 읽기 - 시간초과 질문입니다.

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

public class Main {
    static int N, S, M;

    static int[] VOLUME;

    static long[][] DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 곡 수
        S = Integer.parseInt(st.nextToken()); // 시작 볼륨
        M = Integer.parseInt(st.nextToken()); // 최대 볼류

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

        DP = new long[N + 1][M + 1]; // [곡 순서][볼륨]
    }

    static long executeByTopDown(int idx, int vol) {
        // 조건, 초기항 처리
        if(vol < 0 || vol > M) return -1;
        if(idx == N) return vol;
        
        // 값이 있을 경우 리턴
        if(DP[idx][vol] != -2) return DP[idx][vol];

        // 값이 없을 경우 재귀 호출
        return DP[idx][vol] = Math.max(
                executeByTopDown(idx + 1, vol + VOLUME[idx + 1]),
                executeByTopDown(idx + 1, vol - VOLUME[idx + 1])
        );
    }


    public static void main(String[] args) throws Exception {
        input();
        
        for(int i = 0; i <= N; i++) Arrays.fill(DP[i], -2);
        
        System.out.println(executeByTopDown(0, S));
    }   
}