BOJ[백준] - 1495 - 기타리스트
https://www.acmicpc.net/problem/1495
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 |
#include <stdio.h>
int a[101];
char dp[101][1001];
int main()
{
int N, S, M, i, j, ans = -1;
scanf("%d %d %d", &N, &S, &M);
for(i = 1; i <= N; i++)
scanf("%d", &a[i]);
// assign digit 1 for the all of possible cases
dp[0][S] = 1;
for(i = 1; i <= N; i++)
{
for(j = 0; j <= M; j++)
{
if(dp[i - 1][j])
{
if(j - a[i] >= 0)
dp[i][j - a[i]] = 1;
if(j + a[i] <= M)
dp[i][j + a[i]] = 1;
}
}
}
for(i = 0; i <= M; i++)
if(dp[N][i])
ans = i;
printf("%d", ans);
return 0;
} |
cs |
'Algorithm 문제풀이 > BOJ [백준] 문제풀이' 카테고리의 다른 글
BOJ[백준] - 1520 - 내리막 길 (0) | 2017.07.15 |
---|---|
BOJ[백준] - 1509 - 팰린드롬 분할 (0) | 2017.07.15 |
BOJ[백준] - 1463 - 1로 만들기 (0) | 2017.07.15 |
BOJ[백준] - 1328 - 고층 빌딩 (0) | 2017.07.15 |
BOJ[백준] - 1126 - 같은탑 (0) | 2017.07.15 |