[ 백준 - 19941 ] 햄버거 분배
난이도 : S3
Link : https://www.acmicpc.net/problem/19941
Tag : Greedy
문제 탐색하기
- 식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K일때 햄버거를 먹을 수 있는 사람의 최대수를 구하는 게 목표이다.
- N은 1이상 20,000이하, K는 1이상 10이하이다.
시도 1 ( 성공 😲)
시간복잡도⏰
이미 Greedy알고리즘이라는 것을 알고있지만 아무것도 모른다고 가정해보려고합니다.
사람(P)는 K거리만큼의 모든 위치를 확인하여 햄버거를 선택할 수 있습니다.
최대 K가 10일때 10 * 2 = 20칸을 확인해야합니다. 만약 20칸 내에 양쪽으로 햄버거가 20개 있다고 생각해봅시다.
그렇다면 한 사람이 햄버거를 선택하는 20개의 경우의 수가 있습니다.
다음 사람은 어떨까요? 마찬가지로 최악의 경우 20개의 경우의 수가 있습니다.
또 다음 사람도 20개......
식탁의 길이가 20,000일때 사람이 1000명이라고 가정해봅시다. 각각의 사람들이 햄버거를 선택할 수 있는 경우의 수는 2^1000..
즉, 시간내에 완전 탐색으로는 불가능 하다고 판단 할 수 있습니다.
그렇다면 다음으로는 DP를 생각해볼 수 있겠지만 아직 DP는 배우지 않았기 때문에 생략 하겠습니다.
이런 상황속에서 시간을 단축시키기 위해 Greedy를 사용할 수 있습니다.
구현 방법
햄버거를 최대한 많은 사람이 먹을 수 있으려면 어떻게 해야할까요? 직관적으로 제가 생각했을 때 최대한 앞쪽에서부터 먹으면 됩니다.
앞쪽에서 먹는다면 가장 오른쪽인 사람도 남아있는 햄버거를 먹을 수 있는 확률이 높아질 것입니다. 사람마다 선택할 수 있는 햄버거의 거리가 다른것도 아니니 왼쪽 사람이 먹을 수 있는 햄버거중 최대한 왼쪽의 햄버거를 먹는다면, 오른쪽에 있는 사람은 먹을 수 있는 확률이 높아집니다.
핵심은 '현재 내가 가장 왼쪽의 햄버거를 먹어주는게, 다음 사람을 위한 최선의 선택' 이라는 것입니다.
이렇게 모든 사람의 최선의 선택을 통해 최대한 많은 사람이 햄버거를 먹을 수 있을 것입니다.
세부 구현 사항
1. 주어진 테이블에서 왼쪽부터 탐색한다.
2. 사람일 경우 현재 자신의 위치에서 -K~K 까지 탐색하며 가장 먼저 발견된 햄버거를 먹는다. (해당 위치 방문 표시 & 먹은 사람수 1증가)
3. 먹은 사람수를 출력한다.
import java.io.IOException;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int count = 0;
StringBuilder table = new StringBuilder(sc.next());
for (int i = 0; i < n; i++) {
char c = table.charAt(i);
// 사람일 때
if (c == 'P') {
// 왼쪽부터 탐색
for (int j = -k; j <= k; j++) {
if (i + j < 0 || i + j >= n) {
continue;
}
if (table.charAt(i + j) == 'H') {
table.setCharAt(i + j, 'E'); // 먹음 표시
count++;
break;
}
}
}
}
System.out.println(count);
}
}
구현에 어려움은 없었고 table.charAt(i + j) 인덱스를 처음에 j로 잘못 설정하여 수정하였습니다.
항상 인덱스를 주의 해야하는 것 같습니다.
먹음 표시할때마다 문자열이 수정이 되기 때문에 String 대신에 StringBuilder를 사용하였습니다.
마무리
난이도가 올라가고 어떤 문제가 주어질 때, 어떤 문제에서 Greedy를 사용해서 풀어야할지 선택하는 능력이 중요할 것 같습니다.
추가로 인덱스는 항상 알고리즘 문제를 풀때 주의 깊게 사용해야할 것 같습니다.