문제 풀이

이차원 배열을 이용해 풀이한다.
d[i][j]에서 i번째 음악에 j번째 볼륨이 될 수 있는지 없는지 1과 0으로 나타낼 것이다.
초기엔 s의 볼륨으로 시작하므로 d[0][s] = 1로 설정해주고, 그 이후로는 0이상 m이하의 볼륨을 모두 순회하면서 0 미만 또는 m이 넘지 않는 선에서 가능한 모든 볼륨의 경우를 체크 해준다.

문제 링크

boj/1495

소스코드

PS/1495.cpp

#include<iostream>
#include<algorithm>
using namespace std;


int arr[101];
int d[101][1001];
int main()
{
	int n, s, m;
	cin >> n >> s >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}
	
	d[0][s] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			if (d[i - 1][j])
			{
				if(j+arr[i]<=m)
				d[i][j + arr[i]] = 1;
				if(j-arr[i]>=0)
				d[i][j - arr[i]] = 1;
			}
		}
	}
	
	int ans = -1;
	for (int i = 0; i <= m; i++)
	{
		if (d[n][i])
			ans = i;
	}
	cout << ans;
}