https://www.acmicpc.net/problem/2251
2251번: 물통
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부
www.acmicpc.net
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
[Java] 자바 TreeSet 사용법 & 예제 총정리
TreeSet이란? JDK 1.2부터 제공되고 있는 TreeSet은 HashSet과 마찬가지로 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 그대로 가
coding-factory.tistory.com
참고 사이트
https://fl0wering.tistory.com/13
2251번 : 물통 [Java]
https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤..
fl0wering.tistory.com
'알고리즘 > 완전탐색' 카테고리의 다른 글
[java 백준] 골드 5/1759번 암호 만들기 (0) | 2022.03.17 |
---|---|
[java 백준] 실버 2 / 1182번 부분수열의 합 (0) | 2022.03.06 |
[java 백준]골드 4/ 1963번 소수경로 (0) | 2022.02.26 |
[java 백준]실버 1/1697번 숨바꼭질 (0) | 2022.02.23 |
[C++ 백준] 실버 5/1436번 영화감독 숌 (0) | 2022.02.21 |
댓글