[백준]5557 1학년 #dp

1. i행 j열의 의미

dp[i][j]는, j번째로 들어온 숫자까지 더하거나 뺏을 때 i가 되는 경우의 수를 나타낸다.

​

2. 점화식

dp[i][j](i는 0~20)는 dp[i][j-1]에서 j번째들어온 숫자만큼을 더하거나 뺀값을 추가해주는 형태로 진행된다.

말이 어려우므로 표로 설명한다.

숫자가 가능한 범위는 0~20이므로 표의 행은 21개, 열은 들어오는 숫자의 개수만큼 확보한다.

<input>
11
8 3 2 4 8 7 2 4 0 8 8

 

(1) 첫번째 input 8에 1을 넣는다

		8
	0	1
0
1
2
3
4
5
6
7
8		1
9
10
11
12
13
14
15
16
17
18
19
20

 

2) 두번째 input은 3이다. 첫번째 input에서 3을 더하고 빼주면 5와 11이 된다. 이 경우들을 더해준다.

		8	3
	0	1	2
0
1
2
3
4
5			1
6
7
8		1
9
10
11			1
12
13
14
15
16
17
18
19
20

 

(3) 세번째 input은 2. 두번째 인풋값들에 2를 더하고 빼준다.

		8	3	2
	0	1	2	3
0
1
2
3				1
4
5			1
6
7				1
8		1
9				1
10
11			1
12
13				1
14
15
16
17
18
19
20

 

4) 이를 N-1 까지 반복해준다. 이때 8행 10열이 10열까지 연산 후 8이되는 경우의 수가 된다.

답은 10이다.

 

3. 소스코드

#include <iostream>
#include <algorithm>

using namespace std;

long long arr[21][101];

int main() {
	int N, temp;
	int add, sub;
	cin >> N;
	for (int j = 1; j <= N; j++) {
		cin >> temp;

		/* 출력확인
		for (int r = 0; r < 21; r++) {
			for (int c = 0; c < 21; c++) {
				cout.width(4);
				cout << arr[r][c] << " ";
			}
			cout << endl;
		}
		cout << endl;
		*/


		// 첫번째 값?
		if (j == 1) {
			arr[temp][j] = 1;
		}
		// 마지막 값?
		else if (j == N) {
			cout << arr[temp][j - 1];
		}
		else {
			for (int i = 0; i <= 20; i++) {
				if (arr[i][j - 1] != 0) {
					// 덧셈?
					add = i + temp;
					if (add >= 0 and add <= 20) {
						arr[add][j] += arr[i][j - 1];
					}
					// 뺄셈?
					sub = i - temp;
					if (sub >= 0 and sub <= 20) {
						arr[sub][j] += arr[i][j - 1];
					}
				}
			}
		}
	}


	return 0;
}