백준 14395번: 4연산

문제링크 :https://www.acmicpc.net/problem/14395

14395번: 4연산

 문제설명 

 

1. s,t 가 주어지고 s를 사칙연산을 통해 t를 만들 수있다면 사칙 기호를  순서대로 출력한다.

2. 예를들어 입력 값이 7 392 이면 7+7= 14 * 14=196 + 196 = 392 가되어 +*+ 를 출력한다.

 

 알고리즘 

 

1. '-','/' 연산은 첫번째에만 수행하면 되므로 처음에 따로처리해준다.

2. 그외에 재귀함수를 이용하여 '*' , '+' 연산 순으로 진행하며 혹시 연산횟수가 적은경우가 발생하면 갱신하고

3. 마지막에 최소 연산횟수에 따르는 연산기호를 순서대로 출력한다.

 

 코드 

# include<iostream>
 
int s, t;
char ans[32];
int minLen = 987654321;
char arr[32];
bool fin = false;
 
void func(int s, int idx) {
    if (s > t)
        return;
    if (s == t) {
        fin = true;
        if (idx < minLen) {
            for (int i = 0; i < idx; i++) {
                ans[i] = arr[i];
            }
            minLen = idx;
        }
        return;
    }
 
    //1일때는 무한루프,31623 이초과하면 범위 초과
    if (s != 1 && s < 31623) {
        arr[idx] = '*';
        func(s * s, idx + 1);
    }
    //5억을 초과하면 범위 초과
    if (s <= 500000000) {
        arr[idx] = '+';
        func(s + s, idx + 1);
    }
}
int main() {
 
    scanf("%d %d", &s, &t);
    if (s == t) {
        printf("0\n");
        return 0;
    }
    
    if (t == 0) {
        printf("-\n");
    }
    else if (t == 1) {
        printf("/\n");
    }
 
    else {
        func(s, 0);
        arr[0] = '/';
        func(1, 1);
        if (fin == false) {
            printf("-1\n");
            return 0;
        }
 
        for (int i = 0; i < minLen; i++) {
            printf("%c", ans[i]);
        }
        printf("\n");
    }
    return 0;
}