[프로그래머스/C++] 올바른 괄호의 갯수

 

 

문제

문제 설명

 

 

풀이

 

[풀이]

 

처음에는 memoization을 이용해 풀려고 했는데 n의 개수가 적어서 단순 재귀로 풀었다.

 

열린 괄호를 넣는 경우와 닫는 괄호를 넣는 경우로 나눌 수 있는데, 만약 열린 괄호를 넣게 된다면 사용할 수 있는 열린 괄호의 개수를 1만큼 줄이고 닫힌 괄호의 사용횟수를 1 늘리면 된다.

 

이후 두 경우의 합을 더하면 현재 열린 괄호와 닫힌 괄호를 사용할 수 있을 때 몇개의 경우의 수가 나오는지 결과를 알 수 있다.

​

[아이디어 정리]

1. 열린 괄호의 개수가 0보다 크면 열린 괄호를 사용하고, 닫힌 괄호의 사용횟수를 1 늘린다.
2. 만약 닫힌 괄호의 개수가 0보다 크면 닫힌 괄호를 사용하고 닫힌 괄호의 사용횟수를 1 줄인다.
3. 위 과정을 반복해 최종 횟수를 return한다.

 

 

Code

 

 

#include <string>
#include <vector>
using namespace std;

int calc(int o, int c)
{
    int returnA=0;
    if (o==0&&c==0)
    {
        return 1;   
    }
    if (o>0)
    {
        returnA+=calc(o-1,c+1);
    }
    if (c>0){
        returnA+=calc(o,c-1);
    }
    return returnA;
}

int solution(int n) {
    int answer = 0;
    return calc(n,0);
}

 

 

 

Code (DP)

 

 

#include <string>
#include <vector>
using namespace std;

vector<vector<int>> DP;
int calc(int o, int c)
{
    
    int returnA=0;
    if (DP[o][c]>0)
    {
        return DP[o][c];   
    }
    if (o>0)
    {
        returnA+=calc(o-1,c+1);
    }
    if (c>0){
        returnA+=calc(o,c-1);
    }
    DP[o][c]=returnA;
    return returnA;
}

int solution(int n) {
    DP=vector<vector<int>>(n+1,vector<int>(n+1,0));
    DP[0][0]=1;
    int answer = 0;
    return calc(n,0);
}

 

 

---

 

추가할 코드가 많지 않아 memoization을 활용해 더 시간을 줄여서 풀어봤다

 

 

프로그래머스