algospot MORSE

문제 링크입니다:https://algospot.com/judge/problem/read/MORSE

확실히 난이도:상과 난이도:중은 차이가 있는 것 같습니다.

이 문제는 오버플로를 막기 위해 최대치를 미리 선정해둔 것과 다이나믹 프로그래밍을 사용하지 않는 풀이가 인상적이였습니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

//모든 모스 신호를 만드는 완전 탐색 알고리즘

/*

//signal: 지금까지 만든 신호

//con: 더 필요한 - 개수

//pro: 더 필요한 o의 개수

void generate(int con, int pro, string s)

{

        if (con == 0 && pro == 0)

        {

               cout << s << endl;

               return;

        }

        if (con > 0)

               generate(con - 1, pro, s + "-");

        if (pro > 0)

               generate(con, pro - 1, s + "o");

}

*/

 

//k-1개 건너뛰고 첫 번째 신호를 출력하는 알고리즘

/*

int skip;

//skip개를 건너뛰고 출력

void generate(int con, int pro, string s)

{

        //기저 사례: skip<0

        if (skip < 0)

               return;

        //기저 사례:con=pro=0

        if (con == 0 && pro == 0)

        {

               //더 건너뛸 신호가 없는 경우

               if (skip == 0)

                       cout << s << endl;

               skip--;

               return;

        }

        if (con > 0)

               generate(con - 1, pro, s + "-");

        if (pro > 0)

               generate(con, pro - 1, s + "o");

}

*/

 

//k-1개 건너뛰고 첫 번째 신호를 출력하는 알고리즘 개선

//K의 최대값 +100, 오버플로를 막기 위해 이보다 큰 값은 구하지 않는다

const int MAX = 1000000000 + 100;

int binary[201][201]; //이항계수

int skip; //얼마나 건너뛸 것인가

 

//필요한 이항계수 미리 계산

void calcBinary(void)

{

        memset(binary, 0, sizeof(binary));

        for (int i = 0; i <= 200; i++)

        {

               binary[i][0] = binary[i][i] = 1;

               for (int j = 1; j < i; j++)

                       binary[i][j] = min(MAX, binary[i - 1][j - 1] + binary[i - 1][j]); //수학공식

        }

}

 

//skip개를 건너뛰고 출력

void generate(int con, int pro, string s)

{

        //기저 사례:skip<0

        if (skip < 0)

               return;

        //기저 사례:con=pro=0

        if (con == 0 && pro == 0)

        {

               if (skip == 0)

                       cout << s << endl;

               skip--;

               return;

        }

        if (binary[con + pro][con] <= skip) //건너뛸 수가 이항계수보다 크면

        {

               skip -= binary[con + pro][con]; //건너뛸 수를 재설정

               return;

        }

        if (con > 0)

               generate(con - 1, pro, s + "-");

        if (pro > 0)

               generate(con, pro - 1, s + "o");

}

 

//다이나믹 프로그래밍을 이용하지 않은 풀이

/*

//con개의 -, pro개의 o로 구성된 신호 중 skip개를 건너뛰고

//만들어지는 신호 반환

string kth(int con, int pro, int skip)

{

        //con==0인 경우 나머지 부분은 전부 o

        if (con == 0)

               return string(pro, 'o');

        if (skip < binary[con + pro - 1][con - 1]) //-로 시작하고 건너 뛸 숫자가 이항계수보다 작을 경우

               return "-" + kth(con - 1, pro, skip);

        return "o" + kth(con, pro - 1, skip - binary[con + pro - 1][con - 1]);  //binary[con+pro-1][con-1]는 이미 건너뛰었으니 skip - binary[con+pro-1][con-1]

}

*/

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               int con, pro;

               string result;

               cin >> con >> pro >> skip;

               skip--;

               calcBinary();

               generate(con, pro, result);

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략