BOJ) 계란으로 계란치기

계란으로 계란치기

16987번: 계란으로 계란치기

풀이

 

이 문제가 너무 좋은 점은, 테스트 케이스가 충분히 주어졌기 때문이다. 그래서 그런지 정답 비율이 꽤나 높다.

문제가 제시한 조건을 살펴보면, 계란이 일렬로 나열되어있고 가장 왼쪽 계란부터 오른쪽 끝까지 순차적으로 들어서 계란판에 있는 다른 계란을 내려 치는 것이다.

두 계란의 내구도는 각각 상대 계란의 무게만큼 감소하게 된다.

한번 내리친 다음에, 손에 들고있던 계란을 내려놓고 다음 계란을 든다.

이때, 조건이 손에 쥔 계란이 깨지지 않은 경우에만 내려치는 조건을 실행한다. 또한, 계란판에 깨지지 않은 계란들만 내려쳐야한다.

 

이 조건만 생각하면 어렵지 않았다. 다만, 조금 고생했던 것은(?) 깨진 계란을 세주는 시점이었다.

처음에는 손에 쥔 계란이 제일 오른쪽 계란인 경우에 세주면 되기 때문에, 해당 시점에서만 세주었었다.

하지만, 이미 마지막 계란이 깨져있는 상태라면, 해당 인덱스로 가지 않는다는 문제를 발견하고 계란을 손에 쥐고 깬 다음 깨진 계란을 다 세주었다.

 

이 방법이 가능한 이유는, 총 계란의 갯수가 8밖에 되지 않았기 때문이다. 8개 안에서는 꽤나 효율적인 코드지만, 더 증가한다면 좋지 않을 것 같다. 하지만, 이 문제에서 짠것을 고도화 시킬 것도 아니기 때문에, 문제에서 주어진 조건을 만족시키는 것도 중요하다고 생각한다.

 

코드

 

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

public class Main {
    private static int ANSWER;

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

        for(int i=0; i<size; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            eggs[i][0] = Integer.parseInt(st.nextToken());  // 내구도
            eggs[i][1] = Integer.parseInt(st.nextToken());  // 무게
        }

        solution(size, eggs);
        br.close();
    }

    private static void solution(int size, int[][] eggs) {
        ANSWER = 0;
        crashEggs(0, size, eggs);
        System.out.println(ANSWER);
    }

    private static void crashEggs(int now, int size, int[][] eggs) {
        if(now < size) { // out of idx 방지
            if (eggs[now][0] > 0) {   // 손에 든 계란이 깨지지 않은 경우만
                for (int i = 0; i < size; i++) {
                    if (eggs[i][0] > 0 && i != now) {    // 깨지지 않은 계란일 경우에만 친다
                        eggs[i][0] -= eggs[now][1]; // i의 내구도를 now의 무게만큼 줄여준다.
                        eggs[now][0] -= eggs[i][1]; // now의 내구도를 i의 무게만큼 줄여준다.
                        crashEggs(now + 1, size, eggs);
                        eggs[i][0] += eggs[now][1];
                        eggs[now][0] += eggs[i][1];
                    }
                }
            } else {
                crashEggs(now+1, size, eggs);
            }
        }
        int cnt =0;
        for(int i=0; i<size; i++) {
            if(eggs[i][0] <=0) {
                cnt++;
            }
        }
        ANSWER = Math.max(cnt, ANSWER);
    }
}