14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, ��
www.acmicpc.net
- N 과 M 시리즈 처럼, 재귀를 통해서 한 자리씩 채워나가는 백트래킹 문제이다.
- 숫자의 경우는 주어진 순서대로만 사용하기 때문에, 재귀함수에서 자릿수를 증가시킬 때 해당 자리의 숫자를 사용하면 된다.
- 주어진 사용 가능한 연산자들에 대해서 하나씩 골라야 한다.
- 사용 가능한 연산자가 있으면 그 연산자를 사용 처리 하고, 값을 적절히 구해주어 재귀 호출을 해준 뒤, 재귀가 끝나고 돌아오는 시점에 연산자를 다시 미사용 처리 시켜준다.
#include <iostream>
using namespace std;
int n;
int maxi = -10e8, mini = 10e8;
int numbers[11];
int remain_ops[4];
void check(int size, int value) // size = 이번에 정할 자릿수, value = 지금까지 고른 연산자들로 구한 값
{
if(size == n) // 모든 자릿수를 다 정했을 때
{
if(value < mini) mini = value; // 최댓값과 최솟값 갱신해주고 종료
if(value > maxi) maxi = value;
return;
}
for(int i = 0 ; i < 4 ; i++) // +-*/ 4개에 대해서 사용할게 있는지 검사
{
if(remain_ops[i] > 0) // 사용가능하다면
{
remain_ops[i]--; // 연산자 하나 사용
int nextValue = value;
if(i == 0) nextValue += numbers[size]; // 각 연산자에 맞게 값에 추가 연산
else if(i == 1) nextValue -= numbers[size];
else if(i == 2) nextValue *= numbers[size];
else nextValue /= numbers[size];
check(size + 1, nextValue); // 이번 연산에 구한 값을 넘겨주면서 다음 자릿수를 구함
remain_ops[i]++; // 이번 반복에 썼던 연산자 되돌림
}
}
}
int main(void)
{
cin >> n;
for(int i = 0 ; i < n ; i++) // 수 입력
cin >> numbers[i];
for(int i = 0 ; i < 4 ; i++) // 연산자 갯수들 입력
cin >> remain_ops[i];
check(1, numbers[0]); // 맨 처음 값은 첫번째 숫자값으로 주고 2번째 자리부터 백트래킹 시작
cout << maxi << '\n' << mini << '\n';
}
- 5등 소스코드 참고 : www.acmicpc.net/source/10510964
- 거의 똑같이 풀어서 기분이 좋다.
#include <cstdio>
int n, a[13];
int maxi = -10e8;
int mini = 10e8;
int x, y, z, w;
void f(int s, int g)
{
if(s == n)
{
if(g > maxi) maxi = g;
if(g < mini) mini = g;
}
if(x) { x-- ; f(s + 1, g + a[s+1]) ; x++; }
if(y) { y-- ; f(s + 1, g - a[s+1]) ; y++; }
if(z) { z-- ; f(s + 1, g * a[s+1]) ; z++; }
if(w) { w-- ; f(s + 1, g / a[s+1]) ; w++; }
}
int main()
{
scanf("%d", &n);
for(int i = 1 ; i <= n; i++)
{
scanf("%d", &a[i]);
}
scanf("%d %d %d %d", &x, &y, &z, &w);
f(1, a[1]);
printf("%d %d", maxi, mini);
}
'PS > BOJ' 카테고리의 다른 글
[백준] 14889.cpp : 스타트와 링크 (0) | 2020.09.07 |
---|---|
[백준] 10815.cpp : 숫자 카드 (0) | 2020.09.06 |
[백준] 2193.cpp : 이친수 (0) | 2020.09.04 |
[백준] 1504.cpp : 특정한 최단 경로 (0) | 2020.09.03 |
[백준] 17144.cpp : 미세먼지 안녕! (0) | 2020.09.02 |