대경권 대학생 프로그래밍 경진대회 2번 with 프로그래머스

오랜만에 알고리즘 문제를 푸니 기분이 좋아 대회 리뷰를 남긴다. 1번은 너무 단순한 구현 문제라 생략한다.

전형적인 dp 문제. 

첫번째 입력 예제인 [1,1,1,1] 문제를 (0, [1,1,1,1])로 두고 (1, [1,1,1])과 (-1, [1,1,1]) 경우로 나누는 방법으로 recursive property를 찾아 문제를 해결했다. 

코드

#include <string>

#include <vector>

#include <memory.h>

using namespace std;

int d[102][1001*2], N;

vector<int> input;

int dp(int state, int value){

    int index_value = value + 1001;

    int &ret = d[state][index_value] ;

    if (ret != -1) 

        return ret;

    if (state == N)

        return value == 0;

    

    int result = 0;

    result += dp(state+1, value+input[state]);

    result += dp(state+1, value-input[state]);

    result %= 100000;

    return ret=result;

}

int solution(vector<int> numbers) {

    input = numbers;

    N = input.size();

    memset(d,-1,sizeof(d));

    

    return dp(0, 0);

}