반응형
🔺 문제
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
import java.util.*;
import java.io.*;
public class Main {
static int N, max = Integer.MIN_VALUE;
static int[] durability, weight;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
durability = new int[N]; // 내구성 배열
weight = new int[N]; // 무게 배열
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
durability[i] = Integer.parseInt(st.nextToken());
weight[i] = Integer.parseInt(st.nextToken());
}
back(0);
System.out.println(max);
}
private static void back(int depth) {
// 마지막 계란인 경우
if(depth == N) {
int cnt = 0;
for(int i = 0 ; i < N ; i++)
if(durability[i] <= 0) // 깨진 계란 개수 구하기
cnt++;
max = Math.max(max, cnt);
return;
}
// 내구성이 0 이하면, 다음으로 넘어가기
if(durability[depth] <= 0)
back(depth + 1);
else {
boolean broken = false; // 깰 계란 있는지 확인용 변수
for(int i = 0 ; i < N ; i++) {
if(i == depth || durability[i] <= 0) // 같은 계란이거나 내구성이 0 이하인 경우, 깰수 X
continue;
broken = true; // 깰 계란 존재
// 두 계란 내구성 감소
durability[i] -= weight[depth];
durability[depth] -= weight[i];
back(depth + 1);
// 다음 경우의 수 위해 원상복구
durability[i] += weight[depth];
durability[depth] += weight[i];
}
// 깰 계란이 없으면, 다음으로 넘어가기
if(!broken)
back(depth + 1);
}
}
}
|
cs |
✅ 해결 아이디어
✔ 백트래킹 & 브루트포스
- for문 안에서 연산을 하고, 조건에 맞춰 재귀호출
🔺 다른 풀이들
max를 구하는 방법이 약간 다르다.
💬 느낀 점
기본은 브루트포스를 잘 하고 조건문을 빠뜨리지 않고 쓰는 것 같다.
조합/순열 구하는 단순 백트래킹 문제는 풀겠는데
이렇게 조금이라도 조건을 더하면 못 풀다니...
다음 복습 때는 혼자 힘으로 풀고 싶다!
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 240601 |
(+240601 2회독 : 15676KB, 188ms)
개인적으로 이 풀이가 더 깔끔하니 좋은 것 같당.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
import java.util.*;
import java.io.*;
public class Main {
static int N, answer;
static int[] S,W;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
S = new int[N]; // 계란 내구도
W = new int[N]; // 계란 무게
for(int i = 0 ; i < N ; i++) {
st = new StringTokenizer(br.readLine(), " ");
S[i] = Integer.parseInt(st.nextToken());
W[i] = Integer.parseInt(st.nextToken());
}
dfs(0, 0); // 0번째 계란부터 시작, 깨진 계란 수
System.out.println(answer); // 깰 수 있는 최대 몇 개의 계란
}
private static void dfs(int depth, int cnt) { // cnt: 깨진 계란 수
// 마지막 계란까지 다 들었으면 종료
if(depth == N) {
answer = Math.max(answer, cnt);
return;
}
// 손으로 든 계란이 이미 깨졌거나, 모든 계란이 이미 다 꺠진 경우 > 다음 계란 들기
if(S[depth] <= 0 || cnt == N-1) {
dfs(depth + 1, cnt);
return;
}
int tmpCnt = cnt; // 깨진 계란 수 원상복구 위해 저장용
for(int i = 0 ; i < N ; i++) {
// 손으로 들고 있는 계란 = 부딪히려고 하는 계란인 경우, 계란이 이미 깨져있는 경우 통과
if(i == depth || S[i] <= 0) continue;
// 계란 부딪히기
S[i] -= W[depth];
S[depth] -= W[i];
if(S[depth] <= 0) cnt++; // 손에 든 계란이 깨지면 +1
if(S[i] <= 0) cnt++; // 타겟이 된 계란이 깨지면 +1
dfs(depth + 1, cnt); // 다음 계란 들기
// 원상복구
S[i] += W[depth];
S[depth] += W[i];
cnt = tmpCnt;
}
}
}
|
cs |
(참고)
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1522번: 문자열 교환 (0) | 2023.09.07 |
---|---|
[백준/JAVA] 16435번: 스네이크버드 (0) | 2023.09.07 |
[백준/JAVA] 1448번: 삼각형 만들기 (0) | 2023.09.05 |
[백준/JAVA] 3986번: 좋은 단어 (0) | 2023.09.05 |
[백준/JAVA] 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 (0) | 2023.09.05 |