반응형
[문제링크]
https://www.acmicpc.net/problem/1541
[문제]
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
[입력]
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
[출력]
첫째 줄에 정답을 출력한다.
[예제 입력 1]
55-50+40
[예제 출력 1]
-35
[예제 입력 2]
10+20+30+40
[예제 출력 2]
100
[예제 입력 3]
00009-00009
[예제 출력 3]
0
[설명]
이 문제는 그리디알고리즘 문제다.
문제를 해결하는 가장 큰 핵심은 - 로 문자열을 나눈 뒤 - 뒤에 있는 +들을 모두 더해서 음수화 해주어야 한다.
StringTokenizer 방식을 사용하여 먼저 -로 문자열을 나누었고, 다음에 +로 나누어서 +끼리 모두 더해준다.
만약 -가 하나도 없는 문자열의 경우 sum=temp가 되고, -가 하나라도 있는 문자열의 경우 sum에 temp를 빼주어야 한다.
백준 알고리즘 1541번 JAVA풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(),"-");
int sum=Integer.MAX_VALUE;
while(st.hasMoreTokens()) {
int temp=0;
StringTokenizer add = new StringTokenizer(st.nextToken(), "+");
while(add.hasMoreTokens()) {
temp+=Integer.parseInt(add.nextToken());
}
if(sum==Integer.MAX_VALUE) {
sum=temp;
}else {
sum-=temp;
}
}
System.out.println(sum);
}
}
궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.
반응형
'알고리즘 > GREEDY' 카테고리의 다른 글
BJ_G5_19598_최소 회의실 개수 - Java (0) | 2022.01.24 |
---|---|
BJ_S4_2217_로프 - Java (0) | 2022.01.23 |
BJ_B4_10162_전자레인지 - Java (0) | 2022.01.23 |
BJ_G5_13164_행복 유치원 - Java (0) | 2022.01.23 |
BJ_G5_11000_강의실 배정 - Java (0) | 2022.01.22 |
댓글