코드

n = int(input())
arr = list(map(int, input().split()))

# 덧셈 뺄셈 곱셈 나눗셈
p, m, t, d = map(int, input().split())

# 계산 결과는 결국 주어진 숫자 중 맨 처음 숫자부터 연산이 시작되므로
# 해당 숫자를 기준으로 삼는다
num = arr[0]

# 최댓값, 최솟값
_max = -10e9
_min = 10e9

def dfs(i, num, p, m, t, d):
    global _max, _min
    
    if i == n:
        _max = max(_max, num)
        _min = min(_min, num)
        return
    
    # 연산의 횟수가 0이 아닌 경우에 대하여 모두 계산을 해줌 (브루트포스)
    # 두 번째 argument에서 arr[i]를 연산해주는 이유
    # 기준이 된 num에 선택된 연산의 결과를 누적해서 처리해줘야 함
    # 모든 경우에 대하여 누적 연산된 결과들을 max, min으로 최종적으로 추려냄
    if p:
        dfs(i + 1, num + arr[i], p-1, m, t, d)
    if m:
        dfs(i + 1, num - arr[i], p, m-1, t, d)
    if t:
        dfs(i + 1, num * arr[i], p, m, t-1, d)
    if d:
        # //연산을 사용하면 음수의 경우 원하는 결과가 나오지 않는다
        # 따라서 int() 함수를 사용해서 몫만 얻는 결과를 얻어야 함 (C++14의 기준을 따른다고 명시)
        dfs(i + 1, int(num / arr[i]), p, m, t, d-1)

dfs(1, num, p, m, t, d)
print(_max)
print(_min)

문제 해설

백트래킹과 브루트포스 알고리즘을 활용하여 풀 수 있는 문제.

꾸준히 연습헀던 백트래킹 문제이지만, 활용으로 넘어가니 체감상 난이도가 확 올라간 느낌… 구글링을 통해서 힌트를 얻고 코드를 분석하여 힘겹게 해결하였다.

결국 핵심은 모든 경우를 주어진 숫자의 개수만큼 연산을 하여 최댓값, 최솟값을 계속해서 업데이트한 후, 최종적으로 결과를 출력하므로 브루트포스로 문제를 해결한다는 것을 인지해야 한다.

각 연산마다 남은 횟수별로 조건문을 분기시켜서 모든 연산을 다 처리한 후의 결괏값을 얻을 수 있다.

많은 문제를 연습해봐야겠다 ㅠㅠ

댓글남기기

참고