https://www.acmicpc.net/problem/16987
코드설명
백트래킹 + DFS 문제입니다.
문제로직입니다.
- 각 계란의 깨는 순서에 따라 최대로 계란을 꺠는 갯수가 달라집니다. 그러므로, DFS로 모든 순서를 탐색하는 완전탐색을 진행합니다.
- 만약 현재 깨려는 계란이 깨져있는경우, 아무것도 진행하지않고 다음 계란으로 넘어갑니다.
- 만약 현재 꺠려는 계란이 안깨져있는경우, 다른 계란을 깨면서 simulate를 진행합니다.
- 각 계란을 모두 돌지 않더라도 각 Simulate 마다 항상 깨진 계란의 개수를 갱신해줘야만 합니다. 그래야만, 모든 계란을 꺠지 않더라도 깨진 계란의 최대값을 얻을 수 있습니다.
문제에서 유의해야하는점은
- 각 계란을 깬뒤에 1 2 3 4 5 6 7 8 의 계란이 있으면 모든 계란을 한번씩 꺠진 처리한뒤에 처리하는것인줄알고서 헷갈렸는데 깨지지 않은 다른 계란 중에서 하나를 친다 ( 하나의 계란만 치고 넘어가면 됨 )
- 위의 조건을 인지하지못해서 어떻게 풀어야하는지 고민을 했습니다.
- 문제에서 오류가 났던 부분은, 문제의 각 값들을 찍어보기 위하여 print 문을 했을때 무한 루프가 돌아서 오류인줄알았는데 출력문이 너무 많아서 발생한 경우입니다. 출력문이 계속해서 나온다면, 해당 출력문을 제거하고 출력해보시면 됩니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static int answer = 0;
public static int[][] SiWi;
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());
SiWi = new int[N][2];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
SiWi[i][0] = Integer.parseInt(st.nextToken());
SiWi[i][1] = Integer.parseInt(st.nextToken());
}
simulate(0);
System.out.println(answer);
}
public static void simulate(int nowIdx) {
int max = 0;
for(int i=0;i<N;i++) { //최대의 꺠진 계란을 구하는것이므로 모든 simulate마다 먼저 실행해야합니다.
if(SiWi[i][0] <= 0) { //만약 내구도가 0일시 계란이 꺠진것임으로 증가
max += 1;
}
}
answer = Math.max(answer, max);
if(nowIdx == N) {
return ;
}
if(SiWi[nowIdx][0] > 0) {
for(int i=0; i<N;i++) {
if(i == nowIdx) continue;
if(SiWi[i][0] <= 0) continue;
SiWi[nowIdx][0] -= SiWi[i][1]; //기준계란의 내구도 감소
SiWi[i][0] -= SiWi[nowIdx][1]; //오른쪽계란의 내구도 감소
simulate(nowIdx + 1);
SiWi[nowIdx][0] += SiWi[i][1]; //기준계란의 내구도 원상복구
SiWi[i][0] += SiWi[nowIdx][1]; //오른쪽계란의 내구도 원상복구
}
}else {
simulate(nowIdx + 1);
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1062 가르침 - 백트래킹(BackTracking) + 조합(Combination) JAVA (0) | 2023.08.22 |
---|---|
[백준] 2580 스도쿠 - 백트래킹(Backtracking) + DFS(깊이우선탐색) JAVA (0) | 2023.08.21 |
[백준] 10971 외판원 순회 2 - 백트래킹 + DFS + 외판원 순회 문제(Traveling Salesman Problem (TSP) )JAVA (0) | 2023.08.20 |
[백준] 15486 퇴사 2 - DP JAVA (0) | 2023.08.20 |
[백준] 10844 쉬운 계단 수 - DP JAVA (0) | 2023.08.19 |