[백준 5557번 / C++] 1학년

DP를 활용한 문제이다. 

 

#접근방법 

1. 입력할 수 있는 개수 최대 100과 최대 sum값을 20을 가지기 때문에 dp[101][21] 배열 생성. 
2. 등호를 붙여야 하는 (index-2) 위치에 도달 할 때까지 dfs방식으로 호출한다. ("- 연산", "+ 연산" )

    - sum값이 0보다 작거나 20보다 크면 return 0

    - 이미 메모이제이션이 되있는 경우 해당 값을 return

    - (index-2) 위치에 도달했을 때 마지막값과 sum값이 같으면 return 1 (카운트) 

   

  

    
    
    
    
  
#include <iostream>
using namespace std; 
typedef long long ll; 
int n;
ll dp[101][21]; 
ll d[101];
ll go(int idx, int sum) {
	if (sum < 0 || sum>20)return 0; 
	ll& ret = dp[idx][sum]; 
	if (ret)return ret; 	
	if (idx == n - 2) {
		if (sum == d[n - 1]) {
			return 1;
		}
		return 0; 
	}
	ret += go(idx + 1, sum + d[idx+1]); 
	ret += go(idx + 1, sum - d[idx+1]); 
	return ret; 
}
int main() {
	cin >> n; 
	for (int i = 0; i < n; i++) {
		cin >> d[i]; 
	}
	cout << go(0, d[0]); 
	return 0; 
}

5557번: 1학년