백준 1052, 물병 - Greedy, 시뮬레이션
https://www.acmicpc.net/problem/1052
1. 아이디어
- 그리디 알고리즘
- 가장 작은 물 양의 1L 짜리 물병부터 확인
- 같은 양의 물병이 2개 이상 존재하면, 합침
int[] bottles
에 물 양에 따른 물병 개수 저장
그리디 알고리즘으로 풀이가 가능한 이유
- 물병의 물 양이 1, 2, 4, 8, ..., 2^k 형태의 2의 거듭제곱으로 늘어남
- 작은 물병으로 큰 물병을 만들어낼 수 있으므로, 해를 찾지 못하는 경우가 없음
- 비슷한 문제 유형) 동전 문제
1) 같은 물 양 (index)에 2병 이상이 존재하면, 해당 물 양 x 2 index로 물병을 합침
2) 같은 물 양 (index)에 2병 이상이 존재하지 않으면, 새로 물병을 구입
-
1L 보다 큰, 가장 작은 물 양을 찾음
-
(1L 물병 보다 큰 최소 물병의 물 양) - (현재 보유한 1L 물병의 개수)
만큼 새로운 물병을 구입ex) 현재 1L 물병 1개 보유, 1L 물병보다 큰 최소 물병이 4L 이면
새로운 물병을 (4 - 1) = 3개 구입
=> 새로운 물병을 구입하여, 더 큰 물양의 최소 물병을 만듦
2. 자료구조
int[] bottles
: 해당 물 양에 따른 물병 개수
=> n 최대값 10^7
=> 넉넉하게 [2 * n] 할당
=> 4 x (2 x 10^7) byte = 8 x 10 MB
3. 시간 복잡도
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int n, k; // 처음 소지한 물병 개수 n, 한 번에 이동 가능한 물병 개수 k
static int minCount; // 새로 사야하는 물병 최소 개수
static int bottleCount; // 물이 담겨있는 물통 개수
static int maxWater; // 현재 보유한 물통 중, 최대 물양
static int[] bottles;
// bottles[물 양]: 해당 물 양을 담고있는 물병 개수
// ex) bottles[1] = 13 이면, 1L 물병이 13개
static void solution() {
while (bottleCount > k) {
boolean isSameExist = false; // 같은 물 양의 물병들이 존재하는지
for (int i = 1; i <= maxWater; i++) {
// 같은 물 양의 물병이 2개 이상 존재하는 경우 => 물병 합침
if (bottles[i] >= 2) {
int num = bottles[i]; // 같은 물 양의 물병 개수
bottles[i] = num % 2;
bottles[i * 2] += num / 2;
maxWater = Math.max(maxWater, i * 2);
bottleCount = (bottleCount - num) + (num % 2) + (num / 2);
isSameExist = true;
break;
}
}
// 같은 물 양의 물병이 존재 X => 새로 물병 구입
if (!isSameExist) {
// (1L 물병 보다 큰 최소 물병의 물 양) - (현재 보유한 1L 물병의 개수) 만큼 구입
int newCount = 0;
for (int i = 2; i <= maxWater; i++) {
if (bottles[i] > 0) {
newCount = i - bottles[1];
break;
}
}
bottles[1] += newCount; // 1L 물병 새로 구입
bottleCount += newCount;
minCount += newCount;
}
}
}
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());
k = Integer.parseInt(st.nextToken());
bottles = new int[n * 2];
bottles[1] = n; // 처음) 1L 짜리 물통 n개
bottleCount = n;
maxWater = 1;
if (n <= k) {
System.out.println(0);
return;
}
solution();
System.out.println(minCount);
}
}
Author And Source
이 문제에 관하여(백준 1052, 물병 - Greedy, 시뮬레이션), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@silver_star/백준-1052-물병-Greedy-Simulation저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)