[Algorithm]11 Baekjun 1541紛失括弧

9707 ワード
白駿 グリディ テキストリンク

0、問題


ポテンシャル俊は正数と+,−と括弧で式を構成した.そして勢俊はかっこを全部削除した.
そして勢俊適はかっこをつけて、この式の値を最小限に抑えようとした.
この式の値を最小にするプログラムを適切なかっこで書いてください.
入力
最初の行には数式があります.式は「0」~「9」、「+」、「-」で構成され、最初の文字と最後の文字は数値です.また、2つ以上の演算子が連続して現れず、5桁よりずっと連続した数値はありません.数はゼロから始まることができます.入力式の長さは50以下です.
しゅつりょく
1行目に正解を出力します.

1.アイデア


1)文字列「-」で区切る
2)文字列「+」で区切り、プラス記号
3)最初のsumをretに直接入れ、他のsumを減算
**「-」から「-」の間にすべての数値を加算し、結果全体から最大値を減算します.

2.コア解答


1)文字列「-」で区切る
String sub[] = br.readLine().split("-");
2)文字列「+」で区切り、プラス記号
String add[] = sub[i].split("\\+");
			
for(int j=0; j<add.length; j++) 
			sum += Integer.parseInt(add[j]);
3)最初のsumをretに直接入れ、他のsumを減算
if(ret == Integer.MAX_VALUE)
				ret = sum;
			else
				ret -= sum;

3.コード

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Greedy_12 {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String sub[] = br.readLine().split("-");
		
		int ret = Integer.MAX_VALUE;
		for(int i=0; i<sub.length; i++) {
			int sum = 0;
			
			String add[] = sub[i].split("\\+");
			
			for(int j=0; j<add.length; j++) 
				sum += Integer.parseInt(add[j]);
			
			if(ret == Integer.MAX_VALUE)
				ret = sum;
			else
				ret -= sum;
		}
		
		System.out.println(ret);
		
	}
}

4.結果



成功～

5.エラー



splitの場合、+、*および/はregexにすでに存在する特殊文字なので、区別するために前にを付けなければなりません.
str.split("\\+");   [O]
str.split("+");     [X]
[rhel7] 5. ローカルミラーyumソースの構成
WPF SL C#バックグラウンドライン