백준 문제 24440번 괄호 문자열 표기법 (Small) 문제풀이 c++

https://www.acmicpc.net/problem/24440

24440번: 괄호 문자열 표기법 (Small)

 

문제해석

 

이 문제는 dp문제이다.

dp[n]을 숫자 n을 나타내는 가장 짧고 사전 순으로 앞선 괄호 문자열로 정의를하자.

예를들어 n=25인경우를 살펴보면 

"("+dp[2]+dp[12]+")" , "("+dp[12]+dp[2]+")"

"("+dp[3]+dp[8]+")" , "("+dp[8]+dp[3]+")"

"("+dp[4]+dp[6]+")" , "("+dp[6]+dp[4]+")" 

dp[5]+dp[5]

(여기서 + 는 string concatenate를 의미)

총 7가지의 경우중 길이가 가장 짧은 것들중에서 사전식으로 가장 앞선것을 하나 고르면 된다.

다른 예시로 

n=100인 경우를 살펴보면

dp[2]+dp[50] , dp[50]+dp[2]

"("+dp[3]+dp[33]+")" , "("+dp[33]+dp[3]+")"

dp[4]+dp[25] , dp[25]+dp[4]

dp[5]+dp[20] , dp[20]+dp[5]

"(((("+dp[6]+dp[16]+"))))" , "(((("+dp[16]+dp[6]+"))))"

"(("+dp[7]+dp[14]+"))" , "(("+dp[14]+dp[7]+"))"

"(((("+dp[8]+dp[12]+"))))" , "(((("+dp[12]+dp[8]+"))))"

"("+dp[9]+dp[11]+")" , "("+dp[11]+dp[9]+")"

dp[10]+dp[10]

총 17가지중에서 조건에 맞는 하나가 답이 된다.

문제에서 n의값은 최대 10^6까지인데 사실상 2부터 root 10^6까지만 확인하면되므로 시간제한 내에 풀 수있다.

그렇게 생각하고 첫번째 답을 제출했으나 시간초과가 났다..

 

틀린 코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string solve(int n);
string dp[1000001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,t;
    cin>>t;
    while(t>0)
    {
        cin>>n;
        cout<<solve(n)<<"\n";
        t--;
    }
}
string solve(int n){
    dp[1]="";
    dp[2]="()";
    dp[3]="(())";
    string ans=dp[n];
    if(n<=3)
    {
        return ans;
    }
    if(!dp[n].empty())
    {
        return ans;
    }
    else
    {
        for(int j=2; j*j<=n; j++)
        {
            string s="";
            string p="";
            for(int k=0; k<n-(j*(n/j)); k++)
            {
                s=s+"(";
                p=p+"(";
            }
            string a=solve(j);
            string b=solve(n/j);
            s=s+a+b;
            p=p+b+a;
            for(int k=0; k<n-(j*(n/j)); k++)
            {
                s=s+")";
                p=p+")";
            }
            if(dp[n].empty())
            {
                dp[n]=min(s,p);
            }
            else
            {
                if(s.size()<dp[n].size())
                {
                    dp[n]=min(s,p);
                }
                else if(s.size()==dp[n].size())
                {
                    dp[n]=min({dp[n],s,p});
                }
            }
        }
        ans=dp[n];
        return ans;
    }
}

이렇게 제출했더니 시간초과가 나서 틀렸다.

왜 틀렸는지 몰라서 찾아봤는데 n-(j*(n/j))만큼 ( 문자와 ) 양끝에 붙이는것을 위에 코드처럼

for문을 통해 더했는데 이 방법이 시간을 엄청 잡아먹는다더라...

그래서 저렇게 하면 안되고 append 또는 push_back등 다른방법으로 ( 와 )를 양 끝에 붙이니까 통과했다.

 

정답코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string solve(int n);
string dp[1000001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    dp[1]="";
    dp[2]="()";
    dp[3]="(())";
    int n,t;
    cin>>t;
    while(t>0)
    {
        cin>>n;
        cout<<solve(n)<<"\n";
        t--;
    }
}
string solve(int n){
    string ans=dp[n];
    if(!dp[n].empty())
    {
        return ans;
    }
    if(n<=3)
    {
        return ans;
    }
    else
    {
        for(int j=2; j*j<=n; j++)
        {
            string s="";
            string p="";
            s.append(n-(j*(n/j)),'(');
            p.append(n-(j*(n/j)),'(');
            string a=solve(j);
            string b=solve(n/j);
            s=s+a+b;
            p=p+b+a;
            s.append(n-(j*(n/j)),')');
            p.append(n-(j*(n/j)),')');
            if(dp[n].empty())
            {
                dp[n]=min(s,p);
            }
            else
            {
                if(s.size()<dp[n].size())
                {
                    dp[n]=min(s,p);
                }
                else if(s.size()==dp[n].size())
                {
                    dp[n]=min({dp[n],s,p});
                }
            }
        }
        ans=dp[n];
        return ans;
    }
}

난 append를 사용했지만 틀린코드에서 for문안을 s.push_back('(') s.push_back(')')이렇게 바꾸어도 아마 맞을 것이다.