백준 1443 망가진 계산기

출처: https://www.acmicpc.net/problem/1443

단순하게 중복 없이 모든 경우를 계산하면 얼마일까?

수 n이 연산에 사용된 횟수를 a_n 이라 할 때, (n=2, 3, ..., 9)

중복조합의 최댓값은 p가 30일 때이므로,

a_2 + a_3 + ... + a_9 = 30 

8H30을 계산하면 약 1029만이 나온다. 즉, O(n) 알고리즘으로 시간복잡도를 맞출 수 있다는 뜻이다.

아래는 재귀함수를 이용해서 해결한 C++ 코드이다.

이 때, 중복되는 경우를 없애려면 재귀를 진행할 때 점점 곱하는 숫자가 커지도록 for문을 작성해야 한다.

 

#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int m = 0;
int idx=1;// it는 사용된 연산의 개수// p는 사용해야 하는 연산의 개수// limit은 주어진 자릿수의 수 중 최댓값// num은 지금까지의 연산을 모두 곱한 값// recent는 가장 최근에 곱한 수로 이를 이용해 중복된 경우를 방지
void cal(int it, int p, int limit, int num, int recent){
    if(num>limit){
        return;
    }
    if(it==p){
        if(num>m){
            m = num;
        }
        return;
    }// max(2,recent) 통해서 1이 곱해지는 것을 방지
    for(int i=max(2,recent);i<10;i++){
        if(num*i<limit){
            cal(it+1,p,limit,num*i,i);
        }
    }
}
int main(){
    int d;
    int p;
    scanf(" %d %d",&d,&p);
    m = (int)pow(2,p);
    if(m > pow(10,d)-1){
        printf("-1");
    }
    else{
        cal(0,p,pow(10,d)-1,1,1);
        printf("%d",m);
    }
        
}