Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- build.gradle 설정 오류
- 웹 동작 과정
- DDL DML DCL 차이
- commit message convention
- 빌드관리도구 차이
- www.google.com 검색하면 일어나는 일
- 프로세스
- 모듈로 연산
- 알고리즘 1000000007 나누기
- 기사단원의 무기 파이썬
- finalize 수동 호출
- Spring Security 버전 문제
- 달리기 경주 파이썬
- OOP의 특징
- 프로그래머스 142086
- Spring Security 5
- 빌드관리도구
- @RequestMapping과 @GetMapping
- MySQL LEFT()
- java 동기화
- 이코테2021
- 정규화 장단점
- MySQL RIGHT()
- 백트래킹
- 스프링 부트와 AWS로 혼자 구현하는 웹 서비스
- Python 1000000007
- 기사단원의 무기 제곱근
- 달리기 경주 파이썬 시간초과
- RDBMS와 NoSQL 차이
- PCB
Archives
- Today
- Total
BUILD_SSO
[백준] 14888 연산자 우선순위 python - 구현, 백트래킹 본문
문제링크:https://www.acmicpc.net/problem/14888
예제 입력:
2
5 6
0 0 1 0
예제 출력:
30
30
문제유형: 백트래킹, 구현, DFS
풀이
사칙연산의 모든 경우를 탐색하여 최댓값과 최솟값을 구하는 문제이다.
문제에서 구하고자 하는 것은 주어진 사칙연산을 이용하여 만들 수 있는 모든 결괏값 중 최대와 최소이다.(output)
풀이하며 엄청 헤맸던 문제 중 하나이다.. 단순히 for 문과 if 문을 사용해서 코드를 작성하려 했지만 방법을 찾지 못했고 다른 사람들이 풀어놓은 코드를 참고해서 겨우 제출했다.
* for, if 만으로 작성했다고 하더라도 출력 조건 때문에 터지지 않았을까 의심된다(확실치 않음)
상세 설명:
#사칙연산 수행 함수
def func(add, sub, mul, div, res = 0, i = 0):
덧셈을 사용할 수 있는 경우(add>0), 기호 개수에서 1을 뺀 값(add-1, sub, mul, div)을 func 함수의 인자로 넘겨준다. 이 때, res에 현재까지 계산된 결과 값(덧셈:res+A[i])을 더해주고, 다음 사용할 숫자의 인덱스(i+1)를 넘겨준다.
if add > 0:
#add를 1 감소시키고
func(add - 1, sub, mul, div, res + A[i], i + 1)
이렇게 계속해서 함수를 호출하다가, 모든 기호의 개수가 0이 되면 결과 값을 answer 리스트에 추가한다.
#모든 기호의 개수가 0이 되면 함수를 종료한다.
#예를 들어 add = 2 라면, 덧셈을 최대 2번 수행할 수 있음을 의미한다.
if add == 0 and sub == 0 and mul == 0 and div == 0:
answer.append(res)
return
코드의 마지막 부분에서는, func 함수를 숫자 리스트 A의 첫 번째 숫자(A[0])와 함께 호출하여 모든 경우를 탐색한다.
func(add, sub, mul, div, A[0], 1)
정답 코드:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split()) #사칙연산 기호 개수 입력
answer = []
#res = 현재까지 계산된 결과값, i = 숫자 리스트 A에서 사용할 숫자의 개수
def func(add, sub, mul, div, res = 0, i = 0):
#모든 기호가 0이 된 순간 = 모든 기호를 다 사용한 경우, 현재까지 계산된 결과값을 answer에 append하고 함수를 종료한다.
if add == 0 and sub == 0 and mul == 0 and div == 0:
answer.append(res)
return
if add > 0: #덧셈
func(add - 1, sub, mul, div, res + A[i], i + 1)
if sub > 0: #뺄셈
func(add, sub - 1, mul, div, res - A[i], i + 1)
if mul > 0: #곱셈
func(add, sub, mul - 1, div, res * A[i], i + 1)
if div > 0: #나눗셈
if res > 0:
func(add, sub, mul, div - 1, int(res / A[i]), i + 1)
else:
func(add, sub, mul, div - 1, -int(-res / A[i]), i + 1)
func(add, sub, mul, div, A[0], 1)
print(max(answer))
print(min(answer))
'Problem Solving > Algorithm' 카테고리의 다른 글
[백준] 15649 N과 M(1) python - DFS, 백트래킹 (0) | 2023.03.25 |
---|---|
[백준] 14889 스타트와 링크 python - 백트래킹, 조합 (0) | 2023.03.24 |
Bruteforce: 브루트포스/완전탐색 알고리즘 (+구현) (0) | 2023.03.22 |
Greedy: 그리디 알고리즘 (0) | 2023.03.18 |
[백준] 2178 미로탐색 python - BFS (0) | 2023.03.09 |
Comments