[백준] code.plus(다이나믹 프로그래밍,JAVA)1495번, 기타리스트

문제 링크

1495번: 기타리스트

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

이 문제에 핵심은

 

1. 0 ≤ Volume ≤ M로 소리의 범위입니다.

2. 입력되는 볼륨의 차이를 이용하여 +, -을 진행하여 조절이 끝난 뒤 가장 큰 볼륨의 크기를 결과로 출력한다.

3. 볼륨의 시작 크기는 S로 시작합니다.

 

 

알고리즘 진행 순서.

 

1. 입력되는 볼륨의 차이와 N, S, M을 저장합니다.

 

2. 각 볼륨의 차이를 +, -을 진행하여 최소값을 DP[][]에 저장합니다.

 

3. DP[0][S]의 값을 결과로 출력합니다.

 

 

DP[n][value]의 형태

n : n번째 볼륨의 차이

value : 현재 볼륨의 크기

 

 

예제입력 1.

 

1. 입력되는 볼륨의 차이와 N, S, M을 저장합니다.

 

N = 3

S = 5

M = 10

 

V₁ = 5

V₂ = 3

V₃ = 7

 

2. 각 볼륨의 차이를 +, -을 진행하여 최소값을 DP[][]에 저장합니다.

 

초기 볼륨의 형태 : DP[0][5]

 

V₁ = 5

+ : DP[1][10]

-  : DP[1][0]

 

V₂ = 3

+ : DP[2][3]

-  : DP[2][7]

 

V₃ = 7

+ : DP[3][10](볼륨의 크기 : 10)

-  : DP[3][0](볼륨의 크기 : 0)

 

모든 볼륨의 차이를 적용한 뒤 10, 0이 나왔으며 가장 큰 볼륨의 크기 10이 DP[0][5]에 저장됩니다.

 

3. DP[0][S]의 값을 결과로 출력합니다.

 

DP[0][5] = 10을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 볼륨에 대한 정보를 저장하였습니다.
• search함수를 실행하여 볼륨의 최대값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search는 재귀와 DP를 통해서 각 볼륨의 차이를 +, -을 진행합니다.
• search는 DP에 모든 볼륨을 조절한 최대값을 저장합니다.

 

import java.util.*;
import java.io.*;
public class Main {
    static int[][] DP;	//메모이제이션 배열, DP[n번째 볼륨의 차이][현재 볼륨의 크기]
    static int[] volume;	//볼륨의 차이 저장하는 배열
    static int N,S,M;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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];
        DP = new int[N][M+1]
        //DP값 Integer.MIN_VALUE 초기화;
        for(int i=0;i<N;i++)
            Arrays.fill(DP[i], Integer.MIN_VALUE);
        st = new StringTokenizer(br.readLine());
        //입력되는 볼륨의 차이 저장
        for(int i=0;i<N;i++)
            volume[i] = Integer.parseInt(st.nextToken());

        bw.write(search(0, S) + "");	//N개의 볼륨의 차이 조절 후 최대값 저장
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
    //재귀를 통해서 각 볼륨의 차이를 +, -를 진행하여 모두 조절하였을 때 가장 큰 값을 구하는 함수
    static int search(int index, int value){
        //볼륨의 범위를 벗어난 경우
        if(value > M || value < 0)
            return -1;

        if(index==N)	//모든 조절이 끝날 때
            return value;

        if(DP[index][value]!=Integer.MIN_VALUE)	//이미 방문한 볼륨의 크기일 때
            return DP[index][value];

        //DP[][]의 볼륨의 크기를 조절하면서 최대값을 저장
        DP[index][value] = Math.max(DP[index][value],
                Math.max(search(index+1, value + volume[index]), search(index+1, value-volume[index])));

        return DP[index][value];	//최대값 반환
    }
}