반응형
[모의 SW 역량테스트] 숫자 만들기
1. 이해하기
- N개의 숫자가 적혀 있는 게임 판이 있고, +,-,*,/ 의 연산자 카드를 숫자 사이에 끼워 넣어 다양한 결과 값을 구한다.
- 연산자의 우선 순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.
- 연산자 카드를 사용하여 수식을 계산했을 때, 그 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고, 두 값의 차이를 구하는 문제.
- 완전탐색 문제.
2. 구현하기
-
숫자 사이에 모든 연산자를 넣어보며 그 때의 최솟값과 최댓값을 구한다.
- 연산자는 주어진 갯수만 사용할 수 있으므로 그 이상을 사용한다면 적절한 값을 리턴해준다.
void set_min_max_val(const RET t, int& min_val, int& max_val) { min_val = min(min_val,t.min); max_val = max(max_val,t.max); } RET solve(int index, int plus, int minus, int mul, int div, int res) { if(plus < 0 or minus < 0 or mul < 0 or div < 0) return {MAX,-MAX}; if(plus == 0 and minus == 0 and mul == 0 and div == 0) return {res,res}; int min_val = MAX, max_val = -MAX; RET t = solve(index+1,plus-1,minus,mul,div,res+num[index]); set_min_max_val(t,min_val,max_val); t = solve(index+1,plus,minus-1,mul,div,res-num[index]); set_min_max_val(t,min_val,max_val); t = solve(index+1,plus,minus,mul-1,div,res*num[index]); set_min_max_val(t,min_val,max_val); t = solve(index+1,plus,minus,mul,div-1,res/num[index]); set_min_max_val(t,min_val,max_val); return {min_val,max_val}; }
-
구한 최댓값과 최솟값의 차이를 구한다.
int get_diff() { RET res = solve(1,oper[0],oper[1],oper[2],oper[3],num[0]); return abs(res.min-res.max); }
3. 전체 코드
#include <iostream>
using namespace std;
struct RET {
int min,max;
};
const int MAX = 1000000000;
int oper[4];
int num[12];
int N;
int abs(int a) {
return (a<0)?-a:a;
}
void set_min_max_val(const RET t, int& min_val, int& max_val) {
min_val = min(min_val,t.min); max_val = max(max_val,t.max);
}
RET solve(int index, int plus, int minus, int mul, int div, int res) {
if(plus < 0 or minus < 0 or mul < 0 or div < 0) return {MAX,-MAX};
if(plus == 0 and minus == 0 and mul == 0 and div == 0) return {res,res};
int min_val = MAX, max_val = -MAX;
RET t = solve(index+1,plus-1,minus,mul,div,res+num[index]);
set_min_max_val(t,min_val,max_val);
t = solve(index+1,plus,minus-1,mul,div,res-num[index]);
set_min_max_val(t,min_val,max_val);
t = solve(index+1,plus,minus,mul-1,div,res*num[index]);
set_min_max_val(t,min_val,max_val);
t = solve(index+1,plus,minus,mul,div-1,res/num[index]);
set_min_max_val(t,min_val,max_val);
return {min_val,max_val};
}
int get_diff() {
RET res = solve(1,oper[0],oper[1],oper[2],oper[3],num[0]);
return abs(res.min-res.max);
}
void input() {
cin >> N;
for(int i = 0; i < 4; i++) cin >> oper[i];
for(int i = 0; i < N; i++) cin >> num[i];
}
int main() {
int T;
cin >> T;
for(int t = 1; t <= T; t++) {
input();
cout << '#' << t << ' ' << get_diff() << '\n';
}
return 0;
}
'알고리즘 > SW Expert Academy' 카테고리의 다른 글
[모의 SW 역량테스트] 5656. 벽돌 깨기 (0) | 2019.10.18 |
---|---|
[모의 SW 역량테스트] 5653. 줄기세포배양 (0) | 2019.10.18 |
[모의 SW 역량테스트] 4012. 요리사 (0) | 2019.10.18 |
[모의 SW 역량테스트] 4013. 특이한 자석 (0) | 2019.10.17 |
[모의 SW 역량테스트] 4014. 활주로 건설 (0) | 2019.10.17 |