[白俊]#16987卵で卵を打つ

質問する

元プログラマーの基本的な素質は腕立て伏せではできなかったが、仁範は数少ない3対500を超えるプログラマーの一人だった.仁範はBOJでミスを犯すたびに、5回の引体向上の奇跡的な運動プログラムを通じて、脳と筋肉を鍛える.筋肉を鍛えるとき、レシピが本当に大切な仁範を知って、炭水化物の多いご飯やパンのような朝食の代わりに、タンパク質の多い卵羹を食べます.茶碗蒸しを食べるときは卵を割るが、仁範は力が強すぎて、台所の大理石で卵を割ると、卵の殻が支離滅裂になったり、後処理が困難になることが多い.卵を割ってはどうすればいいのか悩んでいる仁範に、良い解決策を教えてくれた.卵で卵を打つことです.仁範は卵の殻がきれいに割れているのを見つけて、これから卵で卵を打って食事の準備をしたいと思っていました.食事の準備をしていた時も、仁範に脳を鍛える良いパズルを教えてくれた.
問題を紹介する前に、卵で卵を打つと何が起こるかを知っておきましょう.卵ごとに一定の耐久性と重量があります.卵で卵を割ると、それぞれの卵の耐久度が相手の卵の重さと等しくなります.そして、耐久度が0以下の瞬間、卵は割れてしまいます.例えば、卵1の耐久度を7、重量を5、卵2の耐久度を3、重量を4とする.卵1ダースで卵2を打つと、卵1の耐久度が4、3になり、卵2の耐久度が5、-2になります.衝突の結果、卵1はまだ割れておらず、卵2は割れていた.
あるヒョンは、仁範に左から順番に卵を並べて、違う卵を1回打って、卵を最大限に割る問題だと話した.具体的には、卵を打つ過程を以下に説明します.
一番左の卵

を持ち上げます.

手に持っている卵は、割れていない他の卵の中で1つ打つ.しかし、手に持っている卵が割れていないか、他の卵がなければ、打たない.その後、手の中の卵を元の位置に置いて、3つ目の過程を行います.

の最近入った右側の卵を手に持って、2番目の過程を再開します.しかし、最近の卵が一番右側にある卵であれば、卵を打つ過程を終了する.

この過程を通じて、できるだけ多くの卵を割って、これから仁範が毎朝解く謎です.そして、仁範が見つけた答えが正しいかどうかを確認しようとするヒョンがいた.一列に並んだ卵の耐久度と重さを順番に与えると、せいぜいいくつかの卵を割ることができます.

入力

1行目には、卵の数を表すN(1≦N≦8)が与えられる.次のN行は、卵の耐久性と重量に関する情報を提供する.i+1行では、左からi行目の卵の耐久性Si(1≦Si≦300)と重量Wi(1≦Wi≦300)が1つのスペースを隔てている.

しゅつりょく

1行目は人範が破れる卵の最大数を出力します.

入力例1

3
8 5
1 100
3 5

サンプル出力1

3

入力例2

3
1 100
8 5
3 5

サンプル出力2

2

入力例3

1
123 45

サンプル出力3

0

入力例4

8
222 117
176 92
287 6
284 81
221 96
263 96
188 40
225 1

サンプル出力4

4

入力例5

6
65 281
272 145
233 175
229 12
99 88
142 159

サンプル出力5

6

入力例6

8
161 36
248 93
233 13
241 122
285 91
260 25
221 14
233 42

サンプル出力6

3

入力例7

3
213 295
153 24
15 233

サンプル出力7

3

入力例8

8
44 11
116 73
121 54
49 232
69 136
159 242
109 172
28 31

サンプル出力8

8

入力例9

6
100 1
100 1
100 1
100 1
100 1
100 1

サンプル出力9

0

に答える

この問題は,Brootforsアルゴリズムを用いてすべての場合の数を求めた後,最大値を見つければ解ける問題である.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int[] weight;
    static int[] hp;
    static int N;
    static int max = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        weight = new int[N];
        hp = new int[N];

        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split(" ");
            hp[i] = Integer.parseInt(input[0]);       //내구도
            weight[i] = Integer.parseInt(input[1]);   //
        }

        dfs(0);

        System.out.println(max);
    }

    public static void dfs(int temp) {
        if(temp==N) {
            int sum = 0;

            for(int i=0; i<N; i++) {
                if(hp[i]==0)
                    sum++;
            }

            max = Math.max(max, sum);

            return;
        }

        boolean flag = false;
        for(int i=0; i<N; i++) {
            if(i==temp) continue;

            if(hp[i]!=0) {
                flag = true;
                int a = hp[temp] - weight[i];
                int b = hp[i] - weight[temp];

                if(a>0) {
                    hp[temp] -= weight[i];
                }

                else {
                    hp[temp] = 0;
                }

                if(b>0) {
                    hp[i] -= weight[temp];
                }

                else {
                    hp[i] = 0;
                }

                boolean flag2 = false;
                for(int j=temp+1; j<N; j++) {
                    if(hp[j]!=0) {
                        flag2 = true;
                        dfs(j);
                        break;
                    }
                }
                if(!flag2)
                    dfs(N);

                hp[temp] = a+weight[i];
                hp[i] = b+weight[temp];
            }
        }

        if(!flag)
            dfs(N);
    }
}