글 읽기 - 시간초과

zmfldlwl 8년 전 0

혹시 이 문제도 DP(memoization)으로 풀어야 하나요?

단순 재귀로는 해결 안될까요?

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>

using namespace std;

int n;
//A,B,C,D,E,F,G,H,I,J가 가리키는 숫자
int alpha[20];
char input[60][20] = { 0, };
bool check[20];

bool flag[20];
long long t_res;

void REQ(int loc, int num)
{
    alpha[loc] = num;
 
    int cc = 0;

    for (int i = 0; i < 10; i++)
    {
        if (flag[i])
            cc++;
    }

    if (cc == 10)
    {
        long long res = 0;
        //설정된 숫자들가지고 계산
        for (int i = 0; i < n; i++)
        {
            int len = strlen(input[i]);
            for (int j = 0; j < len; j++)
            {
                long long tt = alpha[input[i][j] - 65];
                
                //pow 반환값이 int를 벗어나기 때문에
                for (int k = 0; k < len - 1 - j; k++)
                    tt *= 10;
                
                res += tt;
            }
        }

        if (t_res < res)
            t_res = res;

        return;
    }


    for (int i = 0; i < 10; i++)
    {
        if (!flag[i])
        {
            flag[i] = true;
            REQ((loc + 1) % 10, i);
            flag[i] = false;
        }
    }
}

int main()
{

    cin >> n;


    for (int i = 0; i < n; i++)
    {
        cin >> input[i];
        check[input[i][0] - 65] = true;
    }
    //9가 선택될 위치찾기

    for (int i = 0; i < 10; i++)
    {
        memset(alpha, 0, sizeof(alpha));
        memset(flag, 0, sizeof(flag));
        //i번째 알파벳을 9라고 설정
        if (check[i])
        {
            flag[9] = true;
            REQ(i, 9);
        }
    }

    cout << t_res << endl;

    return 0;	/* 반드시 return 0으로 해주셔야합니다. */
}

indioindio 8년 전 0

제가 맞게 이해한건지 잘 모르겠지만 i번째 알파벳에 9를 주고 모든 경우의 수를 다 탐색하는 방법으로는 어렵지 않을까 싶네요

zmfldlwl 8년 전 0

이게 10!이 될경우에는 약 360만번이 수행되야 되기 때문에 문제가 되는데

9위치를 정해줄 경우 9! 약 36만번을 제일 앞에 나온 알파벳들 수만큼 반복하면 될 줄 알았는데

최악의 경우에는 똑같이 10!이 되서 ㅠㅠ 안되네요...

indioindio 8년 전 0

음 ABC + BCA를 직접 손으로 한 번 해보시면 문제해결에 약간 도움이 될 것 같아요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과

zmfldlwl 8년 전 0

indioindio 8년 전 0

zmfldlwl 8년 전 0

indioindio 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말