백준/DP
(c++)백준 5557번: 1학년
Nimgnoej
2020. 9. 18. 14:56
5557번: 1학년
상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀��
www.acmicpc.net
[풀이]
DP로 풀 수 있는 문제였다.
DP[i][j] : i번째 숫자차례에서 덧셈 혹은 뺄셈한 결과가 j인 경우의 수
점화식
DP[i][j+Num[i]] += DP[i-1][j]
DP[i][j-Num[i]] += DP[i-1][j]
#include <iostream>
using namespace std;
int N;
int Num[101];
long long DP[101][21] = { 0, };
void solution() {
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= 20; j++) {
if (j + Num[i] <= 20)
DP[i][j + Num[i]] += DP[i - 1][j];
if (j - Num[i] >= 0)
DP[i][j - Num[i]] += DP[i - 1][j];
}
}
cout << DP[N-1][Num[N]] << '\n';
}
int main() {
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> Num[i];
}
DP[1][Num[1]] = 1;
solution();
return 0;
}