백준 1443번 망가진 계산기

문제 링크입니다: https://www.acmicpc.net/problem/1443

얼핏 봐서는 매우 쉬운 문제이지만 방문 처리가 까다로울 수 있는 문제입니다.

알고리즘은 간단합니다.

1. 1부터 시작해서 2 ~ 9를 P번 곱합니다. 즉, 결과는 8^P개가 나올 수 있다는 뜻!

2. 따라서, 적절히 가지치기를 해줘야합니다.

i) 자릿수가 D를 넘어가는 경우

ii) cnt번 연산했을 때 똑같은 값이 나온 경우가 있는 경우

3. 하지만, boolean 배열을 [1,000,000,000][30]는 크기가 너무 크기 때문에 선언할 수 없습니다.

-> 따라서, map을 이용하여 저장합니다.

4. 초기에 maxNum을 -1로 초기화하고 maxNumber 함수를 호출한 뒤 maxNum을 출력해주면 됩니다.

#include <iostream>

#include <map>

#include <algorithm>

using namespace std;

 

int D, P;

long long maxNum;

map<pair<long long, int>, bool> visited; //({ num, cnt }, true/false)

 

int getLength(long long num)

{

        int result = 0;

        while (num)

        {

                 num /= 10;

                 result++;

        }

        return result;

}

 

void calc(long long num, int cnt)

{

        //기저 사례: 연산 횟수와 결과가 같을 경우, 혹은 범위를 초과

        if (visited.count({ num, cnt }) || getLength(num) > D)

                 return;

       

        visited[{num, cnt}] = true;

        if (cnt == P)

        {

                 maxNum = max(maxNum, num);

                 return;

        }

 

        for (int i = 2; i <= 9; i++)

                 calc(num * i, cnt + 1);

}

 

int main(void)

{

        cin >> D >> P;

 

        maxNum = -1;

        calc(1, 0);

 

        cout << maxNum << "\n";

        return 0;

}

개발환경:Visual Studio 2017

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