BOJ 2629 양팔저울
https://www.acmicpc.net/problem/2629
2629번: 양팔저울
첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는
www.acmicpc.net
0. 문제 개요
추 여러 개와 Target이 주어진다. 추를 조합하여 Target 무게를 만들 수 있는지 확인하는 문제.
1. 문제 해결 아이디어
(1) i번째 추까지 이용하여 무게를 조합하여 그 무게를 set[i] 배열에 집어넣는다. (중복성을 제거하기 위해 set을 이용)
(2) n번째 추까지 탐색했을 때 해당 set[n]배열에 target값이 존재하는지 확인한다.
무게를 조합하는 경우의 수는 다음과 같다.
1) 이전까지 무게 + 현재 추
2) abs(이전까지 무게 - 현재 추) //절대값 차를 이용해 target이 만들어질 수도 있으므로.
-> 이전까지 무게 + target = 현재 추 -> target = abs(현재 추-이전까지 무게)
3) 이전까지 무게 그대로 유지 // 현재 추를 사용하지 않는다.
이를 코드로 구현하면 아래와 같다.
2. 코드
|
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
48
49
50
51
52
53
54
55
56
|
#include <iostream>
#include <set>
#include <vector>
#include <cmath>
using namespace std;
int n, tN;
int a[35];
set<int > set_arr[35];
int flag;
void solve(int pos,int target) {
if (pos == n) { //종결 조건 : 모든 추를 다 탐색했다.
for (int x : set_arr[pos-1]) {
if (x == target) { //조합한 추 무게중 TARGET이 있다면
flag = 1; //FLAG를 설정한다.
}
}
return;
}
set<int> s;
for (int x : set_arr[pos - 1]) { //이전까지 추로 만든 무게들에 대해
set_arr[pos].insert(x + a[pos]); //현재 추를 더한 무게
set_arr[pos].insert(abs(x - a[pos])); //현재 추를 뺀 무게
set_arr[pos].insert(x); //현재 추를 사용하지 않는 무게
}
solve(pos + 1, target); //다음 추를 탐색한다.
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0;i < n;i++) {
cin >> a[i];
}
set_arr[0].insert(0); //처음 추를 사용하지 않았을 때 무게(==0) 삽입
set_arr[0].insert(a[0]); //처음 추의 무게 삽입
cin >> tN;
int t;
for (int i = 0;i < tN;i++) {
cin >> t;
flag = 0;
solve(1, t); //두번째 추부터 탐색.
if (flag == 1) {
cout << 'Y' << ' ';
}
else
cout << 'N' << ' ';
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
3. 나가며...
dp 2차원 배열을 이용해서 풀 수도 있다!
모든 무게의 합을 dp 배열에 저장해 놓는 식으로!