오늘의 문제
https://www.acmicpc.net/problem/14888
나는 백트래킹이…너무..너무 어렵다……
포인트 쳌쳌
- 연산자별 개수를 입력받아 각각의 변수에 저장한다.
- 모든 피연산자(num)를 조회할 수 있도록 인덱스를 하나씩 늘려가며 탐색하는 재귀 함수를 정의한다.
- 재귀 함수 내에서는 마지막 피연산자가 되었을 경우 종료하는 조건과 각 연산자를 하나씩 줄여가며 함수를 호출하는 조건을 넣어준다.
탐색 문제는 아직도 내게 낯설고 풀기 힘든 존재이다.
백트래킹은 물론 이 문제도 구글링을 통해 내가 생각한 풀이 방식과 가장 유사한 코드를 토대로 이해했다..
풀이 코드
import sys
n = int(input())
num = list(map(int, sys.stdin.readline().split()))
add, sub, multi, divi = map(int, sys.stdin.readline().split()) #연산자별 개수
answer = [] #결과값 저장 리스트
def search(result, idx, add, sub, multi, divi):
if idx == n:
answer.append(result)
return
else:
if add > 0:
#덧셈 개수가 남아있다면
search(result + num[idx], idx+1, add-1, sub, multi, divi)
if sub > 0:
#뺄셈 개수가 남아있다면
search(result - num[idx], idx+1, add, sub-1, multi, divi)
if multi > 0:
#곱셈 개수가 남아있다면
search(result * num[idx], idx+1, add, sub, multi-1, divi)
if divi > 0:
#나눗셈 개수가 남아있다면
search(int(result/num[idx]), idx+1, add, sub, multi, divi-1)
search(num[0], 1, add, sub, multi, divi)
#첫번째 채점: 88ms 소요
#print(max(answer))
#print(min(answer))
#두번째 채점: 84ms 소요
#sys.stdout.write(str(max(answer))+'\n')
#sys.stdout.write(str(min(answer)))
#세번째 채점: 84ms 소요
answer.sort()
sys.stdout.write(str(answer[-1])+'\n')
sys.stdout.write(str(answer[0]))
문제 통과 후에 출력 코드에 따라 시간이 어떻게 차이가 나나 궁금해서 세번정도 시도해보았다.
—
채점 결과
