[C++] 백준 1495 기타리스트 DP

#include <iostream>
#include <vector>

#define MAX_MUSIC 101
#define MAX_VOLUME 1001

using namespace std;


int main()
{
	ios::sync_with_stdio(false);

	int N, S, M, result = -1;
	cin >> N >> S >> M;

	int volume[MAX_MUSIC];
	bool max[MAX_MUSIC][MAX_VOLUME];


	for (int i = 1; i <= N; i++)
		cin >> volume[i];

	max[0][S] = true;	//첫번째값

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= M; j++)
		{
			if (max[i][j] == true)
			{
				if (j + volume[i + 1] <= M)
					max[i + 1][j + volume[i + 1]] = true;

				if (j - volume[i + 1] >= 0)
					max[i + 1][j - volume[i + 1]] = true;
			}
		}
	}

	for (int j = M; j >= 0; j--)
	{
		if (max[N][j] == true)
		{
			result = j;
			break;
		}
	}

	cout << result;
}

 

          5
    0         10
  3               7

10                 0

 

위의 순서대로 값이 입력된다.

 

5 -5와 5+5가 가능하므로 10과 0에 true

 

0이 true므로 0 - 3과 0 + 3이지만 0 + 3 만 가능하므로 3에 true

10이 true므로 10 - 3과 10 + 3이지만 10 - 3인 7에 true... 이런식으로 가능한 부분에 true를 해주어

 

가장 큰 값을 찾아낸다.