곡의 개수가 N, 볼륨의 최댓값은 M이므로 동적프로그래밍을 이용하여 시간 복잡도 O(NM)
핵심 아이디어: 모든 볼륨에 대하여 연주 가능 여부 계산
D[i][j+1] => i번째 노래일 때 j 크기의 볼륨으로 연주 가능한지 여부
노래를 순서대로 확인, 매 번 모든 크기의 볼륨을 검사
D[i][j - V[i]] = True if D[i-1][j] = True
D[i][j + V[i]] = True if D[i-1][j] = True
풀이
n, s, m = map(int, input().split())
array = list(map(int, input().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:
continue
if j - array[i - 1] >= 0:
dp[i][j - array[i - 1]] = 1
if j + array[i - 1] <= m:
dp[i][j + array[i - 1]] = 1
result = -1
for i in range(m, -1, -1):
if dp[n][i] == 1:
result = i
break
print(result)
모든 0 <= j < i에 대해, D[i] = max(D[i], D[j] + height[i]) if area[i] > area[j]
이후에 Max Value에서 테이블 역추적
풀이
n = int(input())
array = []
array.append((0, 0, 0, 0))
for i in range(1, n + 1):
area, height, weight = map(int, input().split())
array.append((i, area, height, weight))
array.sort(key=lambda data: data[3])
dp = [0] * (n + 1)
for i in range(1, n + 1):
for j in range(0, i):
if array[i][1] > array[j][1]:
dp[i] = max(dp[i], dp[j] + array[i][2])
max_value = max(dp)
index = n
result = []
while index != 0:
if max_value == dp[index]:
result.append(array[index][0])
max_value -= array[index][2]
index -= 1
result.reverse()
print(len(result))
[print(i) for i in result]
n, k = map(int, input().split()) dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, n + 1): weight, value = map(int, input().split()) for j in range(1, k + 1): if j < weight: dp[i][j] = dp[i - 1][j] else: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)
matcher2.find(); System.out.println(matcher2.group()); // 매칭된 전체가 출력 System.out.println(matcher2.group(0)); // 매칭된 전체가 출력 System.out.println(matcher2.group(1)); // 첫번째 그룹 System.out.println(matcher2.group(2)); System.out.println(matcher2.group(3));
classWorkObject{ publicsynchronizedvoidmethodA(){ System.out.println("ThreadA의 methodA() 작업 실행"); notify(); // 일시정지 상태에 있는 ThreadB를 실행 대기상태로 만듬 try { wait(); // ThreadA를 일시 정지 상태로 만듬 } catch (InterruptedException e) { e.printStackTrace(); } } publicsynchronizedvoidmethodB(){ System.out.println("ThreadB의 methodB() 작업 실행"); notify(); // 일시정지 상태에 있는 ThreadA를 실행 대기상태로 만듬 try { wait(); // ThreadB를 일시 정지 상태로 만듬 } catch (InterruptedException e) { e.printStackTrace(); } } }
