코딩테스트/문제
[백준] 1541번 잃어버린 괄호
스키(ski)
2023. 7. 3. 18:52
문제 내용
https://www.acmicpc.net/problem/1541
1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다
www.acmicpc.net
풀이 과정
-그리디 알고리즘 같다고 판단하였음
1.뺄셈(-) 기호를 기준으로 값이 최소가 되려면 좌항은 최소 우항은 최대가 되어야한다.
2.뺄셈 기호를 기준으로 나눠서 좌항을 최소로 만들어준다면 전체 식은 최소가 된다고 판단하였다.
풀이중 문제점
-이상 없음.
문제점 해결 과정
-이상 없음.
해결 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import sys
sys_input=sys.stdin.readline
input=sys_input().rstrip().split("-") #뺄셈 기호 기준으로 1차 분리
a_input=[]
for i in input:
a_input.append(sum(map(int,(i.split("+"))))) #좌항부터 순서대로 계산
answer=a_input[0]
for i in range(1,len(a_input)): #계산한값들을 순서대로 빼줌
answer-=a_input[i]
print(answer)
|
cs |
주요 개념
- 그리디 알고리즘 (Greedy Algorithm)
- 파싱 (Parsing)