Problem 93 : Arithmetic expressions (35%)

Description

original

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, * , /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2 14 = 4 * (3 + 1 / 2) 19 = 4 * (2 + 3) − 1 36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

간략해석

$a < b < c < d$인 한 자리 수를 4개를 원하는대로 배치하여, (+, -, * , /)와 괄호를 마음대로 사용하여 결과을 연산한다. 이때 1부터 연속된 자연수를 가장 많이 표현할 수 있는 $a, b, c, d$를 구하여라.

Idea & Algorithm

naive idea

우선 총 연산해야할 개수를 우선 구해보자. 우선 $a,b,c,d$의 조합은 Combination으로, 순서는 팩토리얼로, 각 위치 별로 들어갈 연산자는 지수승으로, 그리고 괄호의 순서가 있다.

여기서 조금 어려운 아이디어는 괄호인데, 괄호의 이유를 알면 쉽게 알 수 있다. 괄호는 다른 연산자보다 먼저 연산함을 의미한다. 즉 이는 4개 수 사이에 있는 연산자를 어떤 순서대로 하는가에 대한 문제이다. 그렇다면 이 가짓수는 팩토리얼로 구할 수 있다.

\[10C4 \cdot 4! \cdot 4^3 \cdot 3! = 1935360\]

즉 1,935,360개의 결과값을 연산하면 된다. 어떤 방식으로 구현할 수 있을까.

advanced idea

이 문젠는 구현 연습과 같기에 구현 방법에 대해서 설명하고자 한다.

1. a, b, c, d 구하기 : dfs

a, b, c, d는 4중 포문 또는 재귀함수를 통해 쉽게 구할 수 있다.

재귀함수의 경우에는 1부터 시작하여 1을 포함하는 경우, 1을 포함하지 않는 경우로 나누어서 재귀를 돌리면 된다. 아래의 코드 경우에는 한자리수를 포함하느냐 마느냐이기에 수를 포함시킬때마다 * 10 + idx를 하여 수를 넘겼고 네자리수인 경우 네 수가 포함된 것이니 $a,b,c,d$를 골랐다는 것을 알 수 있다. idx같은 경우는 9까지 포함시키도록 조건문을 포함시켰다.

2. 네 수 순서쌍 고르기 : ck

이 부분은 c++ algorithm헤더의 next_permutation을 사용하였다. 이 함수는 정렬된 배열 또는 벡터에서 다음 순열로 바꿔주는 함수이다. 연산자의 순서 경우에도 후에 이 함수를 사용하였다.

3. 고정된 순서쌍에서 연산값 구하기 : calc

이 경우에는 연산순서와 연산자를 선택하면된다. 연산순서는 위에 설명하였고, 연산자의 종류는 0,1,2,3으로 지정하여 3중 포문으로 케이스르 구하였다.

4. 순서쌍, 연산순서, 연산자가 결정된 식 계산 : calc_detail

이 경우에는 연결리스트처럼 연산을 실행하였는데, v[idx]과 v[idx+1]을 연산하면 v[idx]에 연산결과를 저장하고, v[idx+1] 뒤의 모든 값을 v[i] = v[i+1]과 같은 연산으로 한칸씩 이동시킨다.

이렇게 연산을 하면 v[0]의 값이 연산 결과값이 된다. 단, 주의할 점은 앞에 부분을 연산했을 때, 후에 idx 부분의 처리를 해주어야한다. 앞에 연산한 횟수만큼 -1를 해주어야한다.

5. 연산하기 : op

연산 종류에 따른 번호와 연산할 값을 입력받고 연산결과를 리턴한다. 단 divided by 0에러를 예외처리 해야하고, 이 경우 에러값으로 리턴하였다.

그외

연산에 따른 결과 값은 set에 저장하였고, set에서 iterate하여 합하고 체크하였다. 또한 이 결과값은 중간에 double형이 될 수 있으므로 double로 연산을 하였다. (int)x == x인 경우에 대해서만 set에 insert하였다.

source code

아래는 위 설명에 따른 소스코드다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int ans, len;

const int ERROR_CHECK = 1e5;

double op(int i, double a, double b){
    if(i==0) return a+b;
    if(i==1) return a-b;
    if(i==2) return a*b;
    if(i==3 && b != 0) return a/b;
    return ERROR_CHECK;
}

int calc_detail(vector<double> v, vector<int> order, vector<int> oper){
    for(int i = 0 ; i < 3 ; i++){
        int ord = order[i];
        for(int j = 0 ; j < i ; j++){
            if(order[j]<order[i]) ord--;
        }
        v[ord] = op(oper[i],v[ord],v[ord+1]);
        if(v[ord]==ERROR_CHECK) return 0;
        for(int j = ord+1 ; j < 3 ; j++){
            v[j] = v[j+1];
        }
    }
    if((int)v[0] != v[0] || v[0] <= 0) return 0;
    return (int)v[0];
}

set<int> calc(vector<double> v){
    vector<int> order;
    for(int i = 0 ; i < 3 ; i++) order.push_back(i);
    set<int> s;
    do{
        for(int i = 0 ; i < 4 ; i++){
            for(int j = 0 ; j < 4 ; j++){
                for(int k = 0 ; k < 4 ; k++){
                    vector<int> oper;
                    oper.push_back(i);
                    oper.push_back(j);
                    oper.push_back(k);
                    s.insert(calc_detail(v, order, oper));
                }
            }
        }
    }while(next_permutation(order.begin(),order.end()));
    return s;
}

void ck(int k){
    int val = k;
    vector<double> v;
    while(k){
        v.push_back((double)(k%10));
        k /= 10;
    }
    sort(v.begin(), v.end());
    set<int> s;
    do{
        set<int> tmp = calc(v);
        for(int i : tmp) s.insert(i);
    }while(next_permutation(v.begin(),v.end()));
    for(int i = 1 ; ; i++){
        if(s.count(i)==0){
            if(i>len){
                ans = val;
                len = i;
            }
            return ;
        }
    }
}

void dfs(int idx, int val){
    if(idx==11) return ;
    if(val>=1000){
        ck(val);
        return ;
    }
    dfs(idx+1, val*10+idx);
    dfs(idx+1, val);
}

int main(){
    dfs(1,0);
    cout << ans;

}

Problem 093