백준 5557_1학년(C++)

 

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

5557번: 1학년

[문제 풀이]

DP를 이용하여 문제를 풀었습니다.

1부터 N까지 받은 후에 2부터 N-1까지 돌면서 dp[i][j]에 먼저 체크해주었습니다. 상근이는 0~20까지의 숫자까지만 알기 때문에 j를 21로 크기를 선언하고 - +가 범위를 벗어나는지 보고 벗어나면 무시하고 아니면 더하는 식으로 했습니다.

[코드]

#include<iostream>

using namespace std;

int N;
int arr[101] = { 0, };
long long dp[101][21] = { 0, };

int main() {

	scanf("%d", &N);


	for (int i = 1; i <= N; i++)
		scanf("%d", &arr[i]);

	dp[1][arr[1]]++;

	for (int i = 2; i < N; i++) {
		for (int j = 0; j <= 20; j++) {

			if (dp[i - 1][j] != 0) {
				if (j - arr[i] >= 0) {
					dp[i][j - arr[i]] += dp[i - 1][j];
				}
				if (j + arr[i] <= 20) {
					dp[i][j + arr[i]] += dp[i - 1][j];
				}
			}
		}
	}

	printf("%lld\n", dp[N - 1][arr[N]]);
	return 0;
}