알고리즘/완전탐색
[java 백준] 실버 1/2251번 물통
Meaning_
2022. 2. 27. 20:26
728x90
반응형
https://www.acmicpc.net/problem/2251
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
public static class Water {
int a;
int b;
int c;
public Water(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
}
public static int a, b, c;
public static ArrayList<Integer> ans = new ArrayList<Integer>();
public static boolean[][][] visited = new boolean[201][201][201];
public static void main(String[] args) throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
a = sc.nextInt();
b = sc.nextInt();
c = sc.nextInt();
Queue<Water> queue = new LinkedList<Water>();
queue.add(new Water(0, 0, c));
while (!queue.isEmpty()) {
Water water = queue.poll();
if (visited[water.a][water.b][water.c]) {
continue;
} else {
visited[water.a][water.b][water.c] = true;
}
if (water.a == 0) {
ans.add(water.c);
}
// a,b물통
if (water.a + water.b > a) {
// 1-2 -> 2-5
// a 다 채우고 나머지는 b로
queue.add(new Water(a, water.a + water.b - a, water.c));
} else {
// 전부 a로 옮기기
queue.add(new Water(water.a + water.b, 0, water.c));
}
if (water.a + water.b > b) {
// b 다 채우고 나머지는 a로
queue.add(new Water(water.a + water.b - b, b, water.c));
} else {
queue.add(new Water(0, water.a + water.b, water.c));
}
// b,c물통
if (water.b + water.c > b) {
queue.add(new Water(water.a, b, water.b + water.c - b));
} else {
queue.add(new Water(water.a, water.b + water.c, 0));
}
if (water.b + water.c > c) {
// c다 채우고 나머지는 b로
queue.add(new Water(water.a, water.b + water.c - c, c));
} else {
queue.add(new Water(water.a, 0, water.b + water.c));
}
// a,c물통
if (water.a + water.c > a) {
// a다 채우고 나머지는 c로
queue.add(new Water(a, water.b, water.a + water.c - a));
} else {
queue.add(new Water(water.a + water.c, water.b, 0));
}
if (water.a + water.c > c) {
// c 다채우고 나머지는 a로
queue.add(new Water(water.a + water.c - c, water.b, c));
} else {
queue.add(new Water(0, water.b, water.a + water.c));
}
}
TreeSet<Integer> treeSet = new TreeSet<>();
for (int x : ans) {
treeSet.add(x);
}
Iterator iter = treeSet.iterator();
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
}
}
|
cs |
문제를 풀면서 중요한거 2가지
1) 문제를 제대로 읽자!
첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 구하는건데 이걸 제대로 안보고 계속 c용량만 출력하니까 틀렸습니다만 떴다..
2) 이건 아쉬운건데 문제를 풀어낼 수 있는 방법이 6가지라는걸 빨리 파악하지 못했다.
사실 조금만 직접 써봐도 알수 있는 거였다.(심지어 직접 써봤는데도 파악하지 못함..ㅋ)
지금까지 완전탐색 문제를 풀면서 느낀건 케이스가 유한하게 정해져있고 거기서 풀어낼 수 있는 방법의 가지 수도 유한했다. 남은 완전탐색 문제도 이 생각을 잊지말고 풀자.
그래서 이문제에서 케이스 분류를 해보면
a,b물통끼리 -> a에서 b로/ b에서 a로
b,c 물통끼리->b에서 c로/c에서 b로
c,a 물통끼리->a에서 c로/c에서 a로
더 세부적으로 파고 들면
1)a,b 물통끼리의 경우 (a,b만 생각해준다)
a물통+b물통> a이면 a물통을 다 채워주고 나머지는 b로
a물통+b물통<a 이면 a에 몰아주고, b는 0
a물통+b물통>b 이면 b 물통 다 채워주고 나머지는 a로
a물통+b물통<b이면 b에 몰아주고 a는 0
이걸 3번 반복해주면 끝
Tree set
중복 제거하고 오름차순으로 정렬해주는 자료구조라 한다.
https://coding-factory.tistory.com/555
참고 사이트
https://fl0wering.tistory.com/13
728x90
반응형