[1495번] 기타리스트

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

다이나믹 프로그래밍으로 문제를 해결 할 수 있다.

dp[i][j] :: i번째에서 j의 볼륨을 가질 수 있다면 true, 아니면 false

n 제한은 100, m 제한은 1000이기에 이중 for문으로 충분히 시간 해결이 가능하다.

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
bool dp[102][1002];
int arr[102];
 
int main()
{
    int n, s, m;
    scanf("%d %d %d", &n, &s, &m);
 
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
 
    dp[0][s] = true;
 
    for (int i = 0; i < n; i++)
        for(int vol = 0; vol <= m; vol++)
            if (dp[i][vol])
            {
                if (vol + arr[i + 1] <= m)
                    dp[i + 1][vol + arr[i + 1]] = true;
                if (vol - arr[i + 1] >= 0)
                    dp[i + 1][vol - arr[i + 1]] = true;
            }
 
    int ans = -1;
    for (int vol = 0; vol <= m; vol++)
        if (dp[n][vol])
            ans = vol;
 
    printf("%d", ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>