[백준] 5557-1학년(C++)

문제링크:https://www.acmicpc.net/problem/5557

5557번: 1학년

 

 

dp문제입니다.

수의 범위가 0~20까지 밖에 되지않고 값이 2^63-1 이라고 명시해주었기 때문에 dp로 풀 수 있는 문제였습니다. 

 

• 초기값으로 배열에 처음 값을 넣어줍니다.
• 이전배열에서 이전배열값들에서 현재값을 더하거나 빼서 얻을 수 있는 값들을 현재배열에 저장합니다.
• 이 과정을 반복한후 마지막값의 인덱스의 현재배열값을 출력합니다. 

정답코드입니다.

#include <iostream>
#include <cstring>
using namespace std;

int n = 0, val = 0;
int arr[100] = { 0 };
long long before[21] = { 0 };
long long current[21] = { 0 };

int main() {
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		cin >> arr[i];
	}
	cin >> val;

	before[arr[0]] = 1; //초기값 지정
	for (int i = 1; i < n - 1; i++) {
		memset(current, 0, sizeof(current));
		for (int j = 0; j <= 20; j++) {
			if (before[j] != 0){
				if ((j + arr[i]) <= 20)
					current[(j + arr[i])] += before[j];
				if((j - arr[i]) >= 0)
					current[(j - arr[i])] += before[j];
			}
		}
		for (int j = 0; j <= 20; j++)
			before[j] = current[j];

	}

	cout << current[val] << '\n';
}