[BOJ] [python] 14888: 연산자 끼워넣기

 

 

Idea

주어진 수열과 각 사칙 연산의 가능한 횟수를 입력 받아, 모든 가능한 경우의 수를 탐색하며 최대값과 최소값을 갱신하는 깊이 우선 탐색(DFS) 기법을 사용한다.

 

• 입력 :
  • N: 수열의 길이
  • num_arr: 수열의 요소들
  • add, sub, mul, div: 각각 더하기, 빼기, 곱하기, 나누기 연산을 수행할 수 있는 횟수
• 초기 설정:
  • maximun을 매우 작은 수로 설정하여 결과 중 최대값을 저장
  • minimum을 매우 큰 수로 설정하여 결과 중 최소값을 저장
  • 첫 번째 숫자를 결과로 초기화하고, dfs 함수를 첫 번째 요소 다음 인덱스에서 시작

 

import sys
 
 
def dfs(depth, result, add, sub, mul, div):
  global maximun, minimum
 
  if depth == N:
    maximun = max(result, maximun)
    minimum = min(result, minimum)
    return
 
  if add:
    dfs(depth + 1, result + num_arr[depth], add - 1, sub, mul, div)
  if sub:
    dfs(depth + 1, result - num_arr[depth], add, sub - 1, mul, div)
  if mul:
    dfs(depth + 1, result * num_arr[depth], add, sub, mul - 1, div)
  if div:
    dfs(depth + 1, result // num_arr[depth], add, sub, mul, div - 1)
 
 
input = sys.stdin.readline
N = int(input())
num_arr = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
maximun = -1e9
minimum = 1e9
result = 0
 
dfs(1, num_arr[0], add, sub, mul, div)
print(maximun)
print(minimum)

트러블 슈팅1: 음수 나눗셈 처리

문제 조건 중 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.

일단 무시하고 구현하였더니 파이썬과 C++14에서의 기준이 다르다는 것을 발견 

 

최종 코드

import sys
 
 
def dfs(depth, result, add, sub, mul, div):
  global maximun, minimum
 
  if depth == N:
    maximun = max(result, maximun)
    minimum = min(result, minimum)
    return
 
  if add:
    dfs(depth + 1, result + num_arr[depth], add - 1, sub, mul, div)
  if sub:
    dfs(depth + 1, result - num_arr[depth], add, sub - 1, mul, div)
  if mul:
    dfs(depth + 1, result * num_arr[depth], add, sub, mul - 1, div)
  if div and result<0:
    dfs(depth + 1, -(-result//num_arr[depth]), add, sub, mul, div - 1)
  if div and result>=0:
    dfs(depth + 1, result // num_arr[depth], add, sub, mul, div - 1)
 
 
input = sys.stdin.readline
N = int(input())
num_arr = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
maximun = -1e9
minimum = 1e9
result = 0
 
dfs(1, num_arr[0], add, sub, mul, div)
print(maximun)
print(minimum)

그냥 분기시켜서 간단하게 처리했다.

 

찾아 보니 int(result/num_arr[depth]) 이런 방법으로 처리할 수도 있다고 한다. 

기타

백준에는 파이썬 코드 제출에 2가지 선택지를 준다.

동일한 코드였는데 Python3이랑 PyPy3이랑 시간차이가 2배넘게 났다.

어떤 분의 코드에선 Python3에서 시간초과가 나므로 PyPy3로 제출해야 한다고 하던데..

 

Python3: Python과 C로 구성된 언어로 구현체가 CPython이다. 즉, Python3는 인터프리터이면서 컴파일러 언어이다.

PyPy3: Python3 언어와 문법은 같지만 JIT(Just-In Time) 컴파일 방식을 도입한 것이다. JIT 컴파일이란 프로그램을 실행하기 전에 컴파일 하는 대신, 프로그램을 실행하는 시점에서 필요한 부분을 즉석으로 컴파일 하는 방식이다. 자주 쓰이는 코드를 캐싱하는 기능이 있기 때문에 인터프린터 언어의 느린 실행속도를 개선할 수 있다.

 

대충만 찾아봐도 공부할 게 많은 것 같다!

여기서 정리하기엔 내용이 많아보여서 나중에 따로 정리할까 한다.