[삼성SW Expert Academy] 숫자만들기(파이썬)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE&problemTitle=%EB%AA%A8%EC%9D%98&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

문제 접근

 

모든 경우를 다 구해야하니 

완전탐색을 활용한다.

 

구체적 구현

하나씩 앞에서부터 시착연산이 남아있는지 보면서 계산

사칙연산의 남은 갯수도 신경써야하므로

백트레킹으로 구현한다

 

주의해야하는 점

1. 음수를 나눌 때 나머지값을 계산할 때 주의해야한다

1번 케이스에서 -2/3을 나누면 0이라고 해줬다.

그런데 실제 컴퓨터에서 -2/3이라고 하면 -1이 나온다.

이를 반영하기 위해

2/3은 0이 나온다는 점에 착안해서

현재 값이 음수면 양수로 바꿔서 나눈 다음

다시 음수로 만들어주었다.

 

2.최대, 최소가 음수가 나올 수 있음.

TestCase5의 경우, 최대 최소가 -5 -96 나오기 때문에

최대,최소 초기값 설정에 주의를 써야한다.

 

문제 코드

T = int(input())

def dfs(n,result):
    global mi,ma,nums,numLength,gu

    if n==numLength:
        mi=min(mi,result)
        ma=max(ma,result)

        return
    for i in range(4):
        if gu[i]>0:
            gu[i]-=1
            tmp=result
            if i==0:
                result+=nums[n]

            elif i==1:
                result-=nums[n]

            elif i==2:
                result*=nums[n]

            elif i==3:
                flag=False
                if result<0:
                    flag=True
                    result*=-1
                result//=nums[n]
                if flag:
                    result*=-1
            dfs(n+1,result)
            result=tmp
            gu[i]+=1


# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N=int(input())

    gu=list(map(int,input().split()))

    nums=list(map(int,input().split()))
    numLength=len(nums)
    #최대 최소 초기화 신경쓸것.
    #최댓값이 음수가 나올 수 있기 때문에
    #범위는 -1e9~~1e9로 가정한다.
    #testcase 5번 참조
    mi=1e9
    ma=-1e9

    dfs(1,nums[0])
    answer=abs(ma-mi)

    print("#{} {}".format(test_case,answer))