[python] 14888번 연산자 끼워넣기

ideal dev·2022년 12월 4일

코딩테스트

목록 보기

10/69

1. 문제 링크 및 문제

https://www.acmicpc.net/problem/14888

1-1 문제 요약

: + - * % 의 개수와 배열이 주어질 때 최대값

2. 해결 방법 생각해보자 ...

모든 경우의 수 계산 = 완전탐색

3. 코드

N= int(input())
arr = list(map(int, input().split()))
calarr = list(map(int, input().split()))
MinAns = int(1e9)
MaxAns = int(-1e9)

def dfs(total, idx, plus, minus, multiply, divide):
    global MaxAns, MinAns
    if idx == N :
        MaxAns = max(total, MaxAns)
        MinAns = min(total,MinAns)
        return

    if plus :
        dfs(total + arr[idx], idx+1, plus-1, minus, multiply, divide)
    if minus :
        dfs(total - arr[idx], idx+1, plus, minus-1, multiply, divide)
    if multiply:
        dfs(total * arr[idx], idx+1, plus, minus, multiply-1, divide)
    if divide:
        dfs(int(total/arr[idx]), idx+1 , plus, minus, multiply, divide-1)

dfs(arr[0],1,calarr[0],calarr[1],calarr[2],calarr[3])
print(MaxAns)
print(MinAns)

그림으로 이해

백준 예제입력2 로 이해

맨 마지막 줄 코드 실행

2.dfs(3,1,1,0,1,0) 일 때,
plus 일 때 dfs(arr[0]+arr[1], idx+1, plus-1,minus,mutiply,divide) 실행
== dfs(7,2,0,0,1,0)
multiply 일 때 dfs(arr[0]*arr[1], idx+1, plus,minus,multiply-1,divide) 실행
== dfs(12,2,1,0,0,0)