[알고리즘 / 백준] 1495 - 기타리스트

www.acmicpc.net/problem/1495

1495번: 기타리스트

 

문제는 위와 같으면 이 문제의 경우 곡이 하나씩 진행될 때마다 0 부터 나올 수 있는 모든 볼륨을 확인하여 마지막에 True 인 볼륨 중 가장 인덱스가 큰 볼륨을 찾는 방식으로 문제를 해결할 수 있습니다.

 

예제를 테이블 형태로 살펴보면 다음과 같습니다.

 

1. 길이가 0부터 11(m+1)까지인 배열을 만들고, 처음 볼륨이 5 이므로 인덱스가 5인 경우만 True 로 지정합니다.

2. 다음 볼륨 조정 값이 5이므로 처음 값 중 True 인 인덱스에서 +5, -5 한 인덱스를 True 로 변경합니다.

3. 다음으로 이전 배열에서 값이 True 인 인덱스(0, 10)에 각각 +3, -3 한 인덱스 중 범위 내 인덱스 값을 True 로 변경합니다.

4. 마지막으로 이전 배열에서 값이 True 인 인덱스(3, 7)에 각각 +7, -7 한 인덱스 중 범위 내 인덱스 값을 True 로 변경합니다.

 

이렇게 구한 배열의 마지막 리스트에서 값이 True 인 가장 큰 인덱스를 찾으면 문제를 해결할 수 있습니다.

 

풀이 코드에서는 True, False 대신 1, 0 을 사용하였습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

n, s, m = map(int, stdin.readline().split())
v = list(map(int, stdin.readline().split()))

dp = [[0] * (m + 1) for _ in range(n + 1)]
dp[0][s] = 1

for i in range(1, n + 1):
    for j in range(m + 1):
        if dp[i - 1][j] == 0:  # 기존 값이 0인 경우 패스
            continue
        if j + v[i - 1] <= m:  # 현재 인덱스에 볼륨 값을 +한 경우 범위 안에 있다면
            dp[i][j + v[i - 1]] = 1  # 해당 인덱스(현재 인덱스에 볼륨 값을 +한) 값을 1로 변경
        if j - v[i - 1] >= 0:  # 현재 인덱스에 볼륨 값을 -한 경우 범위 안에 있다면
            dp[i][j - v[i - 1]] = 1  # 해당 인덱스(현재 인덱스에 볼륨 값을 -한) 값을 1로 변경

result = -1
for i in range(m, -1, -1):  # 가장 큰 값을 찾아야 하므로 뒤에서부터 검사
    if dp[n][i]:
        result = i
        break

print(result)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] nsm = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] v = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int[][] dp = new int[nsm[0] + 1][nsm[2] + 1];
        dp[0][nsm[1]] = 1;

        for (int i = 1; i < nsm[0] + 1; i++) {
            for (int j = 0; j < nsm[2] + 1; j++) {
                if (dp[i - 1][j] == 1) {
                    if (j + v[i - 1] <= nsm[2]) {
                        dp[i][j + v[i - 1]] = 1;
                    }

                    if (j - v[i - 1] >= 0) {
                        dp[i][j - v[i - 1]] = 1;
                    }
                }
            }
        }

        int result = -1;
        for (int i = dp[nsm[0]].length - 1; i >= 0; i--) {
            if (dp[nsm[0]][i] == 1) {
                result = i;
                break;
            }
        }

        System.out.println(result);
    }
}