반응형
728x170
//첫번째 풀이 2021.06.07
//두번째 풀이 2022.02.08
//세번째 풀이 2022.06.13
얘도 모든 걸 다 뒤져봐야 하는 문제다.
다만 모든 걸 뒤질 때 어떻게 뒤지느냐가 문제다.
백트래킹, DFS를 사용했다고 보면 된다.
https://www.acmicpc.net/submit/14888/29858716
#맞는 풀이
#include<iostream>
#include<algorithm>
#define MAX 1000000000
using namespace std;
int N;
int num[12];
int oper[4]; // {add, sub, mul, div 순}
//최대 최소
int m = MAX;
int M = -MAX;
//백트래킹 이용같다.
//입력은 현재까지의 연산결과를 받고 사용한 연산자 개수도 입력받는다
void func(int result, int count){
// 종료시점
if(count == N-1){
//연산 끝나고 최댓값, 최솟값 갱신
if(m > result) m = result;
if(M < result) M = result;
return;
}
//func(1번째 숫자,0번 사용)부터 시작한다. -> 숫자는 주어졌고 연산자는 아직 쓰지 않음
for(int i = 0; i<4; i++){
if (oper[i] == 0) continue;
oper[i]--;
if(i == 0){
func(result+num[count+1], count+1);
}else if(i == 1){
func(result-num[count+1], count+1);
}else if(i == 2){
func(result*num[count+1], count+1);
}else{
func(result/num[count+1], count+1);
}
oper[i]++;
}
}
int main(){
cin >> N;
for(int i = 0; i<N; i++){
cin >> num[i];
}
cin >> oper[0] >> oper[1] >> oper[2] >> oper[3];
//숫자 입력과 연산자의 개수 입력받고
func(num[0],0);
cout << M << "\n" << m << "\n";
}
연산자를 고르는 방법을 백트래킹을 이용해 빠짐없이 고르고
연산자를 다 골라서 연산결과가 나올 때마다
최솟값과 최댓값을 갱신해서 풀었다.
핵심은 백트래킹에서 연산을 어떻게 할 것인지, 파라미터를 무엇을 받을 것인지이다.
#다시 풀어본 풀이
#include <bits/stdc++.h>
using namespace std;
int N;
int num[100]; //숫자 100개
//add, sub, mul, div
int oper[4]; //연산자
int ansm = INT_MAX;
int ansM = INT_MIN;
void func(int cnt, int curVal){
if(cnt == N){
ansm = min(ansm, curVal);
ansM = max(ansM, curVal);
return;
}
for(int i = 0; i<4; i++){
if(oper[i] == 0) continue;
oper[i]--;//선택
//진행
if(i == 0){
func(cnt+1, curVal + num[cnt]);
}else if(i == 1){
func(cnt+1, curVal - num[cnt]);
}else if(i == 2){
func(cnt+1, curVal * num[cnt]);
}else if(i == 3){
func(cnt+1, curVal / num[cnt]);
}
oper[i]++; //복원
}
}
int main(){
cin >> N;
for(int i=0; i<N; i++){
cin >> num[i];
}
for(int i = 0; i<4; i++){
cin >> oper[i];
}
func(1,num[0]);
cout << ansM << '\n';
cout << ansm << '\n';
return 0;
}
뭔가 더 간단해진 것 같긴하다.
여기서 어려운 점은 백트래킹함수를 만드는 것인데..
과연 값을 저장해야할까? 를 생각해봐야 한다.
# 세번째 풀이
역시나 비슷하게 풀었다.
진짜 이 문제 푸는 법 까먹었는데.. 똑같이 풀었네
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> vec;
int oper[4];
int maxN = INT_MIN;
int minN = INT_MAX;
void func(int cnt, int result){
if(cnt == N){
maxN = max(maxN, result);
minN = min(minN, result);
return;
}
for(int i = 0; i<4; i++){
switch(i){
case 0:
if(oper[i] != 0){
oper[i]--;
result += vec[cnt];
func(cnt+1, result);
result -= vec[cnt];
oper[i]++;
}
break;
case 1:
if(oper[i] != 0){
oper[i]--;
result -= vec[cnt];
func(cnt+1, result);
result += vec[cnt];
oper[i]++;
}
break;
case 2:
if(oper[i] != 0){
oper[i]--;
int prev = result;
result *= vec[cnt];
func(cnt+1, result);
result = prev;
oper[i]++;
}
break;
case 3:
if(oper[i] != 0){
oper[i]--;
int prev = result;
result /= vec[cnt];
func(cnt+1, result);
result = prev;
oper[i]++;
}
break;
}
}
}
int main(){
cin >> N;
int first = 0;
for(int i = 0; i<N; i++){
int x;
cin >> x;
if(i == 0)first = x;
vec.push_back(x);
}
for(int i = 0; i<4; i++){
int y;
cin >> y;
oper[i] = y;
}
func(1,first);
cout << maxN << '\n';
cout << minN << '\n';
return 0;
}
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 1759번, 암호만들기 : C++ [CPP] ★★★★ (0) | 2022.02.08 |
---|---|
백준, BOJ, 1182번 C++ [CPP] ★★ (4) | 2022.02.08 |
백준, BOJ, 9019번, DSLR : C++ [CPP] (0) | 2022.02.06 |
백준, BOJ, 13549번, 숨바꼭질 3 : C++ [CPP] (0) | 2022.02.06 |
프로그래머스,JadenCase 문자열 만들기: C++ [CPP] ★★ (0) | 2022.01.21 |