5557 1학년

백준 5557 1학년 https://www.acmicpc.net/problem/5557

+,-를 넣어서 마지막 등호가 성립하는 경우의 수를 구하는 문제이다.
중간 계산으로 0이상 20이하인 경우만 성립한다.

이 문제도 + 또는 - 두가지로 경우가 갈리기 때문에 완전 탐색으로 경우를 저장하여 등호가 성립하는 경우에대해서만 출력하면 된다.

DP[N][M] : N번째 까지의 수의 식을 세웠을때 나오는 값 M에 대한 경우의 수

DP[N + 1][M + arr[N + 1]] += DP[N][M];
DP[N + 1][M - arr[N + 1]]  += DP[N][M];
(0부터 20이하의 범위에 해당하는 경우만 저장하면 된다.)

#include <cstdio> long long dp[101][21]; int main(){     int N, arr[101];     scanf("%d", &N);     for (int n = 1; n <= N; n++)         scanf("%d", &arr[n]);     dp[1][arr[1]] = 1;     for (int n = 1; n <= N - 1; n++){         for (int m = 0; m <= 20; m++){             if (dp[n][m] > 0){                 int a, b;                 a = m + arr[n + 1];                 b = m - arr[n + 1];                 if (a >= 0 && a <= 20)                     dp[n + 1][a] += dp[n][m];                 if (b >= 0 && b <= 20)                     dp[n + 1][b] += dp[n][m];             }         }     }     printf("%lld\n", dp[N - 1][arr[N]]);     return 0; } Colored by Color Scripter

cs