[C/C++ 백준 1495번] 기타리스트 (Silver 1)

https://www.acmicpc.net/problem/1495

1495번: 기타리스트

 

각 변수들의 범위가 그렇게 크지 않기에, dp[i][j] (int나 bool로 선언, i번째 곡의 j크기 볼륨이 가능하면 1, 아니면 0을 저장)를 만들어 모두 구해주면 된다. i-1 번째 곡의 j볼륨이 1이면, j+V[i]와 j-V[i]를 체크해 새로운 dp를 만들어주면 된다.

다만 매개변수가 많으니 꼼꼼하게 체크하자.

 

 

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int N, S, M, V[101]={},dp[101][1001]={}, anscnt=-1;
	scanf("%d %d %d", &N, &S, &M);
	for(int i=1; i<=N; i++){
		scanf("%d", &V[i]);
		for(int j=0; j<=M; j++){
			if(i==1){
				if(j==S+V[i] || j==S-V[i])
					dp[i][j]=1;
			}
			else{
				if(dp[i-1][j]==1)
				{
					if(j+V[i]<=M && j+V[i]>=0)
						dp[i][j+V[i]]=1;
					if(j-V[i]<=M && j-V[i]>=0)
						dp[i][j-V[i]]=1;
				}
			}
		}
	}
	for(int k=0; k<=M; k++){
		if(dp[N][k]==1){
			anscnt=k;
		}
	}
	if(anscnt==-1)	printf("-1");
	else	printf("%d",anscnt);
}