Baekjoon 5557 1학년

Link https://www.acmicpc.net/submit/5557/14656614

소스결과 2004 KB / 0 ms

출처 Baekjoon

언어 C++ 71

분류 다이나믹프로그래밍

 

설명

0 ~ 20밖에 모르는 상근이의 엄청난 도전을 응원하며 몇개의 올바른 등식을 만들 수 있는지 확인하자

 

브루트포스로 당연히 안되는걸 알면서 도전은 해보았다. 결과적으로 바로 시간초과가 나오긴한다.

최대 범위가 20이라 다행이다.

모든 경우에 대해서 n번째 위치에서 올바른 값으로 등록이 되는지를 더해주면된다.

 

알고리즘

1. 첫항 - 0번을 1로 초기화한다.

2. 두번째 항 - 1번을 기준으로 + - 를 진행하여 각 경우에 대해서 이전 항 - 이전 시도 를 더해준다.

3. 모든 항에 대해서 반복 후 마지막 항 - n번 에 대한 값을 출력한다.

 

소스코드

 

#include <iostream>

using namespace std;

const short RAN_MIN = 0;
const short RAN_MAX = 20;
const int MAX = 100;

typedef long long ll;

int numbers[MAX];
ll dp[MAX + 1][RAN_MAX + 1];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n; cin >> n;

	for (int i = 0; i < n; i++)
		cin >> numbers[i];

	dp[0][numbers[0]] = 1;

	for (int i = 1; i < n; i++)
		for (int j = 0; j < RAN_MAX + 1; j++) {
			if (dp[i - 1][j]) {
				if (j + numbers[i] <= RAN_MAX) dp[i][j + numbers[i]] += dp[i - 1][j];
				if (j - numbers[i] >= RAN_MIN) dp[i][j - numbers[i]] += dp[i - 1][j];
			}
		}

	cout << dp[n - 2][numbers[n - 1]];

	return 0;
}