백준
백준 5557 1학년
콩순이냉장고
2020. 8. 26. 13:33
문제 URL : https://www.acmicpc.net/problem/5557
5557번: 1학년
문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들��
www.acmicpc.net
문제 접근법 : 마지막 원소를 제외한 나머지 값들을 더하든 빼든 결과값이 마지막 원소와 같은 경우의 수를 구하는 문제입니다. 모든게 n은 100이고 모든입력이
0이라고하면 더하든빼든 상관없이 최대 2^(n-2) 나오지만 결과값은 2^63 -1 까지라고 나와있으므로 입력값을
조절했을껍니다.
결국 + , - 빼서 결과값이 탐색을 해나가는데 탐색과정을 살펴보면 binary tree형태가 구성되기 때문에
backtracking을 이용했습니다. 그렇지만 가지치기를 이용해야하니 반드시 메모이제이션을 이용하는것은 잊지말것
소스코드 :
|
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
|
//By 콩순이냉장고
#include<iostream>
#include <vector>
#include <cstring>
using namespace std;
int n;
vector<int> v;
long long dp[21][100];//메모이제이션 사용하기위해
long long backtrack(int sum, int idx){
if (sum > 20 || sum < 0)
return 0;
if (idx == n - 1)
{
if (sum == v[n - 1])
return 1;
return 0;
}
if (dp[sum][idx] != -1)//메모이제이션 기법을 이용해서 상당히 효율적인 탐색결과가 나옴
return dp[sum][idx];
return dp[sum][idx] = backtrack(sum + v[idx], idx + 1) + backtrack(sum - v[idx], idx + 1);
//binary tree형태가 구성됨 전체탐색은 시간초과
}
void input()
{
cin >> n;
v.resize(n);
for (int i = 0; i < n; i++)
cin >> v[i];
}
void solve()
{
memset(dp, -1, sizeof(dp));
cout << backtrack(v[0], 1) << "\n";
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
모르는것 혹은 궁금한점 혹은 제가 틀린부분이 있다면 언제든 댓글을 이용해주시길 바랍니다.