인프런 커뮤니티 질문&답변

안녕하세요!

17623번 괄호 문제를 풀다가 어려운 점이 생겨 질문드리게 되었습니다.

저는 탑다운 방식으로 접근을 해보았는데요.

괄호를 넣을 수 있는 경우의 수에 따라 dmap값을 비교하여 최소값을 찾는 방식으로 풀어보았습니다.

하지만 서브태스크3을 통과하지 못하네요. 무엇이 문제일까요...? 고민해보아도 쉽게 찾아지지 않습니다.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std; 

int T; 
string dp[1001];

bool check(string before, string after){
	if(before == "" && after == "") return false;
	if(before == "") return true;   
	if(before.size() > after.size()) return true; 
	else if(before.size() < after.size()) return false; 
	return before > after;     
}

string go(int num)
{
    if(num == 0) return "";
    if(dp[num] != "N") return dp[num];
    if(num - 1 >= 0) // 1빼기 -> 0이 아니라면 무조건 통과하는 조건
    {                // dp[i]에 직접 값을 넣는다.
        string temp = go(num - 1);
        if(check(temp + "12", "12" + temp)) dp[num] = "12" + temp;
        else dp[num] = temp + "12";
    } 
    if(num - 2 >= 0) // 2빼기
    {
        string temp = go(num - 2);
        if(check(dp[num], temp + "34")) dp[num] = temp + "34";
        if(check(dp[num], "34" + temp)) dp[num] = "34" + temp;
    }
    if(num - 3 >= 0) // 3빼기
    {
        string temp = go(num - 3);
        if(check(dp[num], temp + "56")) dp[num] = temp + "56";
        if(check(dp[num], "56" + temp)) dp[num] = "56" + temp;
    }
    if(num % 2 == 0) // 2로 나눔
    {
        string temp = go(num / 2);
        if(check(dp[num], "1" + temp + "2")) dp[num] = "1" + temp + "2";
    }
    if(num % 3 == 0) // 3로 나눔
    {
        string temp = go(num / 3);
        if(check(dp[num], "3" + temp + "4")) dp[num] = "3" + temp + "4";
    }
    if(num % 5 == 0) // 5로 나눔
    {
        string temp = go(num / 5);
        if(check(dp[num], "5" + temp + "6")) dp[num] = "5" + temp + "6";
    }
    return dp[num];
}

string getPassing(string num)
{
    string s = "";
    int i = 0;
    while(i < num.size())
    {
        char digit = num[i];
        string d = "";
        if(digit == '1') d = "(";
        else if(digit == '2') d = ")";
        else if(digit == '3') d = "{";
        else if(digit == '4') d = "}";
        else if(digit == '5') d = "[";
        else if(digit == '6') d = "]";
        s += d; 
        i++;
    }
    return s;
}

int main()
{
    fill(dp, dp + 1001, "N");
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        int N;
        cin >> N; 
        string answer = go(N);
        cout << getPassing(answer) << "\n";
    }
    return 0;
}