백준 16987. 계란으로 계란치기

문제 보기

※ 골드 이상의 문제는 문제 요구사항 분석 먼저 하기

문제 분석

• 백트래킹으로 순열을 구하는 구조에 조건 추가
• 계란x, 계란y 충돌 -> 둘 다 깨지거나, 둘 중 하나만 깨지거나
• 내구도 체크하여 카운트 - 누적 합 쌓아가기(임시변수를 cnt에 더하기)
• 다음 계란 집는다 = 다음 순회 시작 = 새로운 dfs 호출
• 계란을 친다 = 내구도 minus 수행 + 깨졌을 시 카운트 누적

조건 체크

1. 가장 왼쪽의 계란을 든다.
2. 손에 들고 있는 계란으로 깨지지 않은 다른 계란 중에서 하나를 친다. 단, 손에 든 계란이 깨졌거나 깨지지 않은 다른 계란이 없으면 치지 않고 넘어간다. 이후 손에 든 계란을 원래 자리에 내려놓고 3번 과정을 진행한다.
3. 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행한다. 단, 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료한다.

• 조건1) 가장 최근에 든 계란이 가장 오른쪽에 위치한 계란일 경우 계란을 치는 과정을 종료
  => base case

• 조건2) 손에 든 계란이 깨졌거나 / 깨지지 않은 다른 계란이 없으면 치지 않고 가장 최근에 든 계란의 한 칸 오른쪽 계란을 손에 들고 2번 과정을 다시 진행
  => 즉, 손에 든 계란이 깨졌거나, 나머지 계란이 다 깨졌을 경우 dfs를 호출

• 조건3) 깨지지 않은 다른 계란 중에서 하나를 친다.
  => 깨진 계란의 경우 치지 않음(내구도 마이너스 연산 하지X)

이를 코드에 조건으로 적용해보기

풀이

package org.server;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
//친다=dfs

public class Eggs {
    static int N;
    static int[] force;
    static int[] weight;
    static int max=Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        force = new int[N];
        weight = new int[N];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            force[i] = Integer.parseInt(st.nextToken());
            weight[i] = Integer.parseInt(st.nextToken());
        }
        //System.out.println(Arrays.toString(force));
        dfs(0,0);//첫번째 계란으로 시작
        System.out.println(max);
    }
    public static void dfs(int start,int cnt){//순열
        if(start==N){//조건1)
            max = Math.max(max,cnt);
            return;
        }
        if(force[start]<=0){
        //조건2) 손에 든 계란이 깨졌을 경우
            dfs(start+1,cnt);
            return;
        }
        boolean flag=false; //조건2) 남은 계란 다 깨졌을 경우
        for(int i=0;i<N;i++){
            if(start==i) continue; //자기자신 pass
            if(force[i]<=0) continue;//조건3) 계란 깨졌을 경우 - 치지않고 넘어가기
            force[start]-=weight[i];
            force[i]-=weight[start];
            flag=true;
            int add = 0;
            if(force[start]<=0) add++;
            if(force[i]<=0) add++;
            dfs(start+1,cnt+add);
            force[start]+=weight[i];
            force[i]+=weight[start];
        }
        if(!flag){//조건3이 쌓여서 조건2) 남은 계란 다 깨졌을 경우 충족
            dfs(start+1,cnt);
        }
    }
}

이슈사항

• 백트래킹 순열 문제를 크게 가져가고 그 안에서 조건 체크
• 이해하고 코드로 구현하기까지 일주일 넘게 본 것 같다.
• 돌려야 할 범위=N=for

효율성 개선 굿..