174. 연산자 끼워 넣기
1. DFS
중복 순열(product) 라이브러리
- 예를 들어 n = 4라고 하면, 사칙 연산 중에서 중복을 허용하여 3개를 뽑아 나열하는 모든 경우를 고려해야 한다.
from itertools import product
n = 4
print(list(product(['+','-','*','/'], reapeat = (n - 1)))
n = int(input())
data = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
#최솟값, 최댓값 초기화
min_value = 1e9
max_value = -1e9
def dfs(i, now):
global min_value, max_value, add, sub, mul, div
#모든 연산자 다 사용한 경우, 최솟값과 최댓값 업데이트
if i == n:
min_value = min(min_value, now)
max_value = max(max_value, now)
else:
#각 연산에 대해 재귀적으로 수행
if add > 0:
add -= 1
dfs(i + 1, now + data[i])
add += 1
if sub > 0:
sub -= 1
dfs(i + 1, now - data[i])
sub += 1
if mul > 0:
mul -= 1
dfs(i + 1, now * data[i])
mul += 1
if div > 0:
div -= 1
dfs(i + 1, int(now / data[i])) #나눌 땐 나머지 제거
div += 1
#연산자는 숫자의 개수보다 1 적으니 1부터
dfs(1, data[0])
print(max_value)
print(min_value)
2. C++
#include <bits/stdc++.h>
using namespace std;
int n;
// 연산을 수행하고자 하는 수 리스트
vector<int> arr;
// 더하기, 빼기, 곱하기, 나누기 연산자 개수
int add, sub, mul, divi;
// 최솟값과 최댓값 초기화
int minValue = 1e9;
int maxValue = -1e9;
// 깊이 우선 탐색 (DFS) 메서드
void dfs(int i, int now) {
// 모든 연산자를 다 사용한 경우, 최솟값과 최댓값 업데이트
if (i == n) {
minValue = min(minValue, now);
maxValue = max(maxValue, now);
}
else {
// 각 연산자에 대하여 재귀적으로 수행
if (add > 0) {
add -= 1;
dfs(i + 1, now + arr[i]);
add += 1;
}
if (sub > 0) {
sub -= 1;
dfs(i + 1, now - arr[i]);
sub += 1;
}
if (mul > 0) {
mul -= 1;
dfs(i + 1, now * arr[i]);
mul += 1;
}
if (divi > 0) {
divi -= 1;
dfs(i + 1, now / arr[i]);
divi += 1;
}
}
}
int main(void) {
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
arr.push_back(x);
}
cin >> add >> sub >> mul >> divi;
// DFS 메서드 호출
dfs(1, arr[0]);
// 최댓값과 최솟값 차례대로 출력
cout << maxValue << '\n' << minValue << '\n';
}
Author And Source
이 문제에 관하여(174. 연산자 끼워 넣기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/174.-연산자-끼워-넣기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
