[SWEA] 4008. 모의 SW 역량테스트 - 숫자 만들기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH

SW Expert Academy

설계

- dfs 완전탐색 

- operator을 남아있는 총알처럼 생각, 총알이 없을 경우 사용할 수 없다.

- 소수점 주의 ( //로 하면 안된다.)

# 최대값 - 최소값
# 나눗셈 소수점은 버린다. / 연산카드 모두 사용

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    operator = list(map(int, input().split()))      # [+, -, *, /]
    arr = list(map(int, input().split()))

    maxV = -100000000
    minV = 100000000

    def dfs(level, sumV):
        global maxV, minV, operator

        if level == N-1:
            maxV = max(maxV, sumV)
            minV = min(minV, sumV)

        for i in range(4):
            if operator[i] > 0:         # 사용할 수 있는 연산자가 남아있는지 확인
                operator[i] -= 1        # 사용한 연산자는 빼준다.
                if i == 0:
                    dfs(level + 1, sumV + arr[level+1])         # 연산에 성공하면 다음 인덱스로 넘어간다.
                elif i == 1:
                    dfs(level + 1, sumV - arr[level+1])
                elif i == 2:
                    dfs(level + 1, sumV * arr[level+1])
                elif i == 3:
                    dfs(level + 1, int(sumV / arr[level+1]))        # 소수점은 버리기 때문에 정수형태로 전환해준다.
                operator[i] += 1        # 다음 경우의 수를 위해 연산자 복구

    dfs(0, arr[0])       # level, sumV
    print(f'#{tc} {maxV-minV}')