4008.숫자 만들기

이번에 풀어볼 문제는 숫자 만들기이다. 오늘은 너무 피곤해서 아무것도 안하려다가 그래도 하나라도 풀자는 마음에

정답률이 높은 문제를 그냥 풀어보았다.. 근데 본의아니게 난이도가 매우 낮은 문제가 나왔다... 크흠.. 

이렇게 쉬운 문제가 나왔을 땐 다른 사람의 코드와 비교하면서 좀 더 쉬운방법이나 다양한 방법을 공부해야겠다.

이 문제는 한마디로 그냥 조합이다. 주어진 연산자와 숫자들을 가지고 조합만 할줄 알면 풀리는 간단한 문제이다.

딱히 중요한 설계도 필요없었던거 같다. 그냥 풀면된다. 알고리즘을 시작한지 얼마안된 사람이라면 풀어봄직하다!

( 물론 그렇다고 나의 코드가 깔끔하거나 대단한건아니다...ㅎㅎ ) 

 

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <algorithm>
 
using namespace std;
 
int T, N, d, b, g, n; // 테스트케이스, 숫자갯수, 더하기, 빼기, 곱하기, 나누기 변수
deque<int> num;  // 숫자가 저장되는 deque
deque<char>giho; // 연산자가 저장되는 deque
int main(){
    freopen("4008.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        cin >> N;
        cin >> d >> b >> g >> n;
        num.clear(); // 초기화
        giho.clear();// 초기화
        while (d + b + g + n != 0){ // 연산자들을 deque에 담는다.
            if (d){
                giho.push_back('+');
                d--;
            }
            else if (b){
                giho.push_back('-');
                b--;
            }
            else if (g){
                giho.push_back('*');
                g--;
            }
            else if (n){
                giho.push_back('/');
                n--;
            }
        }
        int tmp;
        for (int i = 0; i < N; i++){ // 숫자저장
            cin >> tmp;
            num.push_back(tmp);
        }
 
        sort(giho.begin(), giho.end()); // permutation을 하려면 정렬을 해주어야 한다!! 빼먹으면 안됨
        int mx = -987654321; // 최대값 변수
        int mn = 987654321;  // 최소값 변수
        int sum = 0; //계산 결과
        do{
            sum = num[0]; // 첫 값은 그냥 저장
            for (int i = 0; i < giho.size(); i++){ // 기호의 크기만큼 돌림
                if (giho[i] == '+')
                    sum += num[i + 1];
        
                else if (giho[i] == '-')
                    sum -= num[i + 1];
 
                else if (giho[i] == '*')
                    sum *= num[i + 1];
 
                else if (giho[i] == '/')
                    sum /= num[i + 1];
            }
            if (mx < sum) // 최대
                mx = sum;
            if (mn > sum) // 최소
                mn = sum;
            sum = 0;
        } while (next_permutation(giho.begin(), giho.end())); // 순열이 있다면 계속 진행
        cout << "#" << z << " " << mx - (mn) << endl; // 최대와 최소의 차이
    }
    return 0;
}

 

 

 

---

 

< Code 설명 - 재귀 사용 >

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#define MAX 13
 
using namespace std;
 
int T, N;
int yun[4];
int p_yun[MAX];
int max_ans;
int min_ans;
 
void check(int cnt, int num){ // 계산함수(계산 숫자 카운트, 합산 숫자)
    if (cnt == N){ //숫자의 계산이 모두 끝나면
        max_ans = max(max_ans, num); // 최댓값 구함
        min_ans = min(min_ans, num); // 최솟값 구함
        return;
    }
    else{
        if (yun[0]){ // ' + '
            yun[0]--; // 해당 연산자 -1
            check(cnt + 1, num + p_yun[cnt]); // 연산수 +1, 해당연산자로 연산 진행, 재귀
            yun[0]++; // 다른 조합을 위해 다시 연산자 채워놓음
        }
        if (yun[1]){ // ' - '
            yun[1]--; // 해당 연산자 -1
            check(cnt + 1, num - p_yun[cnt]); // 연산수 +1, 해당연산자로 연산 진행, 재귀 
            yun[1]++; // 다른 조합을 위해 다시 연산자 채워놓음
        }
        if (yun[2]){ // ' * '
            yun[2]--; // 해당 연산자 -1
            check(cnt + 1, num * p_yun[cnt]); // 연산수 +1, 해당연산자로 연산 진행, 재귀 
            yun[2]++; // 다른 조합을 위해 다시 연산자 채워놓음
        }
        if (yun[3]){ // ' / '
            yun[3]--; // 해당 연산자 -1
            check(cnt + 1, num / p_yun[cnt]); // 연산수 +1, 해당연산자로 연산 진행, 재귀
            yun[3]++; // 다른 조합을 위해 다시 연산자 채워놓음
        }
    }
}
int main() {
    freopen("4008.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        cin >> N;
        for (int i = 0; i < 4; i++)
            cin >> yun[i]; // 연산자 입력
       for (int i = 0; i < N; i++)
            cin >> p_yun[i]; // 피연산자 입력
 
        max_ans = -987654321; // 최대
        min_ans = 987654321; // 최소
        check(1, p_yun[0]); // 사용된 p_yun의 갯수, 첫 시작숫자(합산) 인자로 함수호출
        cout << "#" << z << " " << max_ans - (min_ans) << endl;
    }
    return 0;
}