본문 바로가기

Problem Solving/문제풀이

[BOJ] 2629 양팔저울

DP 정의는 $DP(i,j)$=i 이하 번호의 추를 사용하여 왼쪽 저울 - 오른쪽 저울의 무게가 j가 되게 할 수 있는가

그러면 $DP(i,j)=DP(i+1,j+weight[i]) || DP(i+1,j-weight[i]) || DP(i+1,j)$라는 점화식이 세워짐. 왼쪽에 올리거나, 오른쪽에 올리거나, 아예 올리지 않거나. 간단한 DP problem


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
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
 
using namespace std;
 
int f(int x)
{
    return x+60000;
}
 
int n,m;
int weight[35];
int cache[35][120000];
 
int dp(int idx, int w)
{
    if(idx==n)
    {
        if(w==f(0)) return 1;
        else return 0;
    }
 
    int& ret=cache[idx][w];
    if(ret!=-1return ret;
 
    int ma=0;
    ma=max(ma,dp(idx+1,w+weight[idx]));
    ma=max(ma,dp(idx+1,w-weight[idx]));
    ma=max(ma,dp(idx+1,w));
    return ret=ma;
}
 
int main()
{
    memset(cache,-1,sizeof(cache));
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&weight[i]);
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        int t;
        scanf("%d",&t);
        printf("%c ",dp(0,f(t))?'Y':'N');
    }
    return 0;
}
 
cs

'Problem Solving > 문제풀이' 카테고리의 다른 글

[BOJ] 11377 열혈강호 3  (0) 2018.09.21
[BOJ] 7579 앱  (0) 2018.09.18
NYPC 예선 후기  (1) 2018.08.31
[BOJ] 10840 구간 성분  (0) 2018.07.19
[BOJ] 2472 체인점  (0) 2018.07.18