[BOJ 백준] 1학년(5557) C++

 

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

5557번: 1학년

 

문제 설명 : 

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

 

입력 : 

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력 : 

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.

 

예제 입력 : 

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

예제 출력 : 

7069052760

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 1학년 5557 
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (101)

using namespace std;

int N; //숫자의 개수

int arr[MAX];
//   dp[ i ] [  j  ]   : i 번째 숫자 배열에서, 연산 결과 j로 가능한 경우의 수 
//                       최종 출력할 답 : dp[  N-2     ] [    arr[N-1]   ]
//                        N-2번째 숫자가  = arr[N-1]의 값이 되는 경우의 수
long long dp[MAX][21];

void input();

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	input();

	// 2. DP 진행
	// 1) 초기값 넣고 시작
	dp[0][arr[0]] = 1;

	// 2) N-2까지 점화식 수행 //   arr[N-1]과 값을 비교하면 됨
	int num;
	for (int i = 1; i < N - 1; i++) {
		// 현재 연산을 수행할 숫자
		num = arr[i];
		// 가능한 숫자의 조합 모두 확인 (0~20) - 음수는 불가
		for (int j = 0; j < 21; j++) {
			
			// 2-1) 플러스는 20 이하면 가능
			if (j + num < 21) {
				dp[i][j] += dp[i - 1][j + num]; 
			}

			// 2-2) 마이너스는 음수 아니어야 가능
			if (j - num >= 0) {
				dp[i][j] += dp[i - 1][j - num]; 
			}
		}
	}

	// 3. 출력
	printf("%lld", dp[N-2][arr[N - 1]]);

	return 0;
}

void input() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
}
#endif