[C/C++] 백준 - 5557번 : 1학년

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

5557번: 1학년

문제

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

 

 

 

 

 

동적계획법으로 해결 가능한 문제이다.

 

메모이제이션을 어떻게 적용시킬지 고민해야한다.

나는 앞에서부터 하나씩 확인해보면서 진행할 것이기 때문에 주어진 수들의 위치를 확인하는 인덱스(1),

앞에서부터 진행하면서 연산을 수행하는 결과값(2), 더할지 뺄지 결정하는 연산의 방법(3)

 

이렇게 총 3가지를 메모이제이션에 적용시키기로 하였고, 

cache배열을 3차원으로 만들어 관리해주었다.

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
vector<int> ps;
ll cache[103][2003][3];

void input() {
	cin >> N;
	ps = vector<int>(N, 0);
	for (int i = 0; i < N; i++) {
		cin >> ps[i];
	}
}

ll path(int index, int sum, int method) {
	if (sum < 0 || sum > 20) return 0;
	if (index == N-1) {
		if (sum == ps[N - 1]) return 1;
		else return 0;
	}
	ll& ret = cache[index][sum][method];
	if (ret != -1) return ret;
	ret = 0;
	ret += path(index + 1, sum + ps[index], 2) + path(index + 1, sum - ps[index], 1);
	return ret;
}

ll solution() {
	memset(cache, -1, sizeof(cache));
	return path(1, ps[0], 0);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}