[백준] 14888번 : 연산자 끼워넣기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

14888번: 연산자 끼워넣기

 

1. 문제 설명

2. 풀이과정

해당 문제는 연산자를 각 수 사이에 넣는 순서에 따라 달라지는 연산의 결과 중 최댓값과 최솟값을 구하는 문제이다.

연산자의 개수에 따라 수많은 조합의 결과가 나오기 때문에 많은 시간이 걸린다.

하지만 우선 모든 조합을 전부 계산해 보며 최댓값과 최솟값을 구해보았다.

 처음 비교할 최댓값에는 현재 문제에서 가능한 최솟값인 -10억을, 최솟값에는 현재 문제에서 가능한 최댓값인 10억을 저장해 주고 이후 각 연산 결과와 비교해 각 최댓값과 최솟값을 저장해 주었다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 순열 함수를 사용하기 위해 permutations() 함수를 불러온다. from itertools import permutations
3. 수의 개수를 입력받고 N = int(sys.stdin.readline())
4. 각 수를 입력받아 리스트로 저장한다. A = list(map(int, sys.stdin.readline().split()))
5. 각 연산자의 개수도 입력받아 리스트로 저장한다. op = list(map(int, sys.stdin.readline().split()))
6. 모든 연산자를 저장할 리스트를 생성하고 li = list()
   연산자 종류만큼 반복하고 for i in range(len(op))
7. 각 연산자의 개수만큼 반복하며 for j in range(op[i])
8. 해당 연산자를 인덱스 번호로 리스트에 추가해 준다. li.append(i)
9. 연산 결과의 최댓값을 저장할 변수를 생성하고 최솟값을 저장한다. MAX = -1000000000
10. 연산 결과의 최솟값을 저장할 변수를 생성하고 최댓값을 저장한다. MIN = 1000000000
11. 모든 연산자를 순열 함수를 활용해 가능한 모든 조합을 구하고 각 경우를 하나씩 불러온다. for i in list(permutations(li))
12. 최종 연산 결과를 저장할 변수를 생성하고 제일 첫 번째 수를 저장한다. result = A[0]
13. 수의 순서를 저장할 변수를 생성하고 다음 수를 지정하기 위해 1을 저장한다. n = 1
14. 불러온 연산자의 조합의 각 연산자를 다시 하나씩 불러오며 for j in i
15. 만약 해당 연산자의 인덱스 값이 0이면 if (j == 0)
16. 다음 수를 연산의 결과에 더해준다. result += A[n]
17. 만약 해당 연산자의 인덱스 값이 1이면 elif (j == 1)
18. 다음 수를 연산의 결과에 빼준다. result -= A[n]
19. 만약 해당 연산자의 인덱스 값이 2이면 elif (j == 2)
20. 다음 수를 연산의 결과에 곱해준다. result *= A[n]
21. 만약 해당 연산자의 인덱스 값이 3이면 elif (j == 3)
22. 연산의 결과를 다음 수로 나눠준 값을 정수형으로 저장한다. result = int(result / A[n])
23. 다음 수를 지정하기 위해 수의 순서를 다음 순서로 넘겨준다. n += 1
24. 해당 연산자의 조합으로 나온 연산의 결과를 현재 최댓값과 비교하여 더 큰 값을 최댓값으로 저장하고 MAX = max(MAX, result)
25. 마찬가지로 현재 최솟값과 비교하여 더 작은 값을 최솟값으로 저장한다. MIN = min(MIN, result)
26. 모든 연산자의 조합에 따른 연산 결과를 모두 확인했다면 그때의 최댓값을 출력하고 print(MAX)
27. 최솟값을 출력한다. print(MIN)

해당 문제를 위 방법으로 해결한 결과 Python3에서는 시간 초과가 발생하였고, PyPy3에서만 통과가 되었다.

하여 아래의 방법으로 다시 풀어보았다.

 

3. 소스코드

import sys
from itertools import permutations

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
op = list(map(int, sys.stdin.readline().split()))

li = list()
for i in range(len(op)):
    for j in range(op[i]):
        li.append(i)

MAX = -1000000000
MIN = 1000000000

for i in list(permutations(li)):
    result = A[0]
    n = 1
    
    for j in i:
        if (j == 0):
            result += A[n]

        elif (j == 1):
            result -= A[n]

        elif (j == 2):
            result *= A[n]

        elif (j == 3):
            result = int(result / A[n])

        n += 1

    MAX = max(MAX, result)
    MIN = min(MIN, result)

print(MAX)
print(MIN)

반응형

4. 다른 풀이

해당 방법은 재귀를 활용해 문제를 해결하였는데, 각 연산자의 개수가 남아있으면 각 연산자를 대입하고 만약 연산할 수를 지정하는 값이 전체 숫자의 개수와 동일해지면 해당 결과에 따른 최댓값과 최솟값을 구한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 수의 개수를 입력받고 N = int(sys.stdin.readline())
3. 각 수를 입력받아 리스트로 저장한다. A = list(map(int, sys.stdin.readline().split()))
4. 각 연산자의 개수도 입력받아 리스트로 저장한다. op = list(map(int, sys.stdin.readline().split()))
5. 각 연산자 조합별 연산을 수행할 함수를 정의한다. def dfs(n, result, plus, sub, mul, div)
6. 함수의 인수로는 연산을 해줄 수의 순서, 현재 연산의 결과, 각 연산자의 개수를 전달해 주었다.
7. 최댓값과 최솟값을 저장해 줄 변수는 함수 외부에서 선언해 주었기 때문에 global 변수로 지정해 주어 함수 안에서도 값을 변경할 수 있도록 해주었다. global MAX, MIN
8. 만약 연산을 해줄 수의 순서가 전체 수의 개수와 동일하면 if (n == N)
9. 더 이상 연산할 수가 없으므로 현재 최댓값과 최종 연산 결과 중 최댓값을 구하고 MAX = max(MAX, result)
10. 현재 최솟값과 최종 연산 결과 중 최솟값을 구한다. MIN = min(MIN, result)
11. 해당 연산자 조합에 따른 연산을 수행했으므로 종료한다. return
12. 연산할 수가 남아있을 때, 만약 덧셈 연산자가 남아있다면 if (plus)
13. 연산할 수는 다음 수로 이동하고, 연산 결과는 해당 수를 현재 연산 결과에 더해준다. 덧셈 연산자를 하나 사용했으므로 개수를 하나 줄여 연산을 수행할 함수를 호출해 준다. dfs(n + 1, result + A[n], plus - 1, sub, mul, div)
14. 여기서 해당 연산자의 순서마다 가능한 모든 연산자의 경우를 모두 구하기 위해 모든 조건문을 if 문으로 작성하였다.
    만약 뺄셈 연산자가 남아있다면 if (sub)
15. 연산할 수는 다음 수로 이동하고, 연산 결과에 해당 수를 현재 연산 결과에 빼준다. 뺄셈 연산자를 하나 사용했으므로 개수를 하나 줄여 연산을 수행할 함수를 호출해 준다.  dfs(n + 1, result - A[n], plus, sub - 1, mul, div)
16. 만약 곱셈 연산자가 남아있다면 if (mul)
17. 연산할 수는 다음 수로 이동하고, 연산 결과는 해당 수를 현재 연산 결과에 곱해준다. 곱셈 연산자를 하나 사용했으므로 개수를 하나 줄여 연산을 수행할 함수를 호출해 준다.  dfs(n + 1, result * A[n], plus, sub, mul - 1, div)
18. 만약 나눗셈 연산자가 남아있다면 if (div)
19. 연산할 수는 다음 수로 이동하고, 연산 결과는 현재 연산 결과를 해당 수로 나눠준 결과를 정수형으로 전달한다. 나눗셈 연산자를 하나 사용했으므로 개수를 하나 줄어 연산을 수행할 함수를 호출해 준다.  dfs(n + 1, int(result / A[n]), plus, sub, mul, div - 1)
20. 연산 결과의 최댓값을 저장할 변수를 생성하고 최솟값을 저장한다. MAX = -1000000000
21. 연산 결과의 최솟값을 저장할 변수를 생성하고 최댓값을 저장한다. MIN = 1000000000
22. 두 번째 수를 지정하는 인덱스 값인 1과, 초기 연산 결과인 첫 번째 수, 각 연산자의 개수를 인수로 하여 함수를 호출해 준다. dfs(1, A[0], op[0], op[1], op[2], op[3])
23. 최종 모든 연산 결과 중 최댓값을 출력하고 print(MAX)
24. 최솟값을 출력한다. print(MIN)

해당 방법으로 문제를 해결한 결과 Python3로도 문제가 여유롭게 해결되었다.

 

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
op = list(map(int, sys.stdin.readline().split()))

def dfs(n, result, plus, sub, mul, div):
    global MAX, MIN

    if (n == N):
        MAX = max(MAX, result)
        MIN = min(MIN, result)
        return
    
    if (plus):
        dfs(n + 1, result + A[n], plus - 1, sub, mul, div)

    if (sub):
        dfs(n + 1, result - A[n], plus, sub - 1, mul, div)

    if (mul):
        dfs(n + 1, result * A[n], plus, sub, mul - 1, div)

    if (div):
        dfs(n + 1, int(result / A[n]), plus, sub, mul, div - 1)

MAX = -1000000000
MIN = 1000000000

dfs(1, A[0], op[0], op[1], op[2], op[3])

print(MAX)
print(MIN)