백준 16987(JAVA)

문제

https://www.acmicpc.net/problem/16987

16987번: 계란으로 계란치기

풀이

백트래킹 문제이다.
적절하게 재귀함수를 이용해서 계란을 칠수있는 모든 경우의 수를 파악해야한다.

어떻게 하면 달걀을 집어서 칠 대상 달걀을 고르는 경우를 생각할수있을까?
일단 어떤식으로 할수있는지 간단하게 생각하자.

달걀 a, b, c, d, e 다섯개가 있다고하자.

a 를 들고 b를 칠수있다.
그다음은 한칸 오른쪽 달걀을 들어야한다.
치는 대상은 아무거나 하나를 칠수있으므로
b를 들고 a를 칠수 있다.(a or b가 깨지지 않고 온전하면)

c도 다시 a 를 칠수있다.

...

a - > b
b -> a
c -> a
d -> a
e -> a
이런식으로 치게된다.(아무 달걀도 깨지지 않았다고 가정하자.)

이렇게 게임이 끝나면(맨오른쪽 달걀을 치고 끝나면)

다른 경우도 확인해야한다.

a - > b
b -> a
c -> a
d -> a
e -> b

이러한 경우도 확인해야겠다.

a - > b
b -> a
c -> a
d -> a
e -> c
이러한 경우도 확인해야하고.

a - > b
b -> a
c -> a
d -> a
e -> d

...

이렇게 탐색을 하며 모든 게임의 경우수를 확인해야한다.

이러한 과정을 보면 생각나는 문제가 있다!!
바로 N과 M 백트래킹 문제이다. - 풀어보기 강추, 난 반복해서 여러번풀었삼!

이런식으로 탐색해 나가며 게임이 끝날 때, 즉 맨 오른쪽 달걀을 치고 끝날 때 깨진 달걀의 개수를 업데이트 해주면 된다.

@@ 참고로 재귀함수 호출이 끝나면 줄어든 두개 달걀의 무게(잡고있는 달걀, 대상 달걀)는 원상복귀 해야한다!!

코드

package training.backtracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main16987 {
    static int N;
    static Egg[] eggs;
    static int max = 0;


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

        eggs = new Egg[N];

        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            eggs[i] = new Egg(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        play(0);

        System.out.println(max);
    }
    static void play(int grabPosition){
        if(grabPosition == N){
            // 맨 오른쪽 끝 계란을 잡고 치면 끝
            max = Math.max(max, countBrokenEggs());
            return;
        }

        if(eggs[grabPosition].s <= 0 || (eggs[grabPosition ].s > 0 && countBrokenEggs() == N - 1))
            // 손에든 달걀이 깨져있거나, 손에든 달걀은 꺠지지않았는데, 나머지 달걀이 모두 깨져있으면 계란치지말고 다음 계란 포이터로 넘어감
            play(grabPosition + 1);
        else {
            // 계란 치기
            for (int i = 0; i < N; i++) {
                if (grabPosition == i) continue; // 자기 자신은 못친다
                if (eggs[i].s <= 0) continue; // 칠 계란이 이미 깨져있음

                //계란2개 모두 무게줄이기
                eggs[grabPosition].s -= eggs[i].w;
                eggs[i].s -= eggs[grabPosition].w;

                play(grabPosition + 1); // recursive

                //계란 2개 무게 원복
                eggs[grabPosition].s += eggs[i].w;
                eggs[i].s += eggs[grabPosition].w;
            }
        }
    }
    static int countBrokenEggs(){
        int count = 0;
        for (Egg egg : eggs) {
            if(egg.s <= 0) count++;
        }
        return count;
    }
}

class Egg{
    int s; // 내구도
    int w; // 무게

    Egg(int s, int w) {
        this.s = s;
        this.w = w;
    }
}