[Java][BOJ 19941] 햄버거 분배

문제 링크

문제 파악

식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오. 첫 줄에 N과 K가 주어지고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)과 H(햄버거)로 주어진다. 

• 1 <= N <= 20000
• 1 <= K <= 10

20 1
HHPHPPHHPPHPPPHPHPHP //8

20 2
HHHHHPPPPPHPHPHPHHHP //7

접근 방법

햄버거	사람	햄버거	사람	햄버거	사람	햄버거	햄버거	사람	사람	햄버거	사람
1	2	3	4	5	6	7	8	9	10	11	12

K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

처음에 그리디로 생각했는데 9번의 경우 가장 가까운 값으로 먹으면 10번이 11번 햄버거를  먹어서 12번이 아무것도 못먹게 된다. 

그래서 백트래킹인건가? dfs로 각 P마다 1-K번 모두 점프 시도해보았다. (근데 가장 가까운 값을 먹는게 아니라 가장 작은 인덱스 값부터 먹는 그리디였으면 가능했다. )

• 처음에는 한 칸 점프, 만약 K가 1보다 크면, 2칸 점프해서 dfs... K칸까지 점프하는 dfs 실행 후 Math.max로 출력

1. String 에서 P를 찾아 이동 가능한 거리를 for문으로 돌면서 먹을 수 있는 지 확인한다.
2. 먹을 수 있으면 햄버거 eaten 표시와 사람별로 먹었는지를 나타내는 pEaten를 True 표시한다.
3. 먹을 수 없거나 H면 idx+1해서 다음 dfs 실행한다.
4. 인덱스가 String 길이가 되면 종료

    static char[] line;
    static boolean[] eaten;
    static boolean[] pEaten;
    
dfs(0,0);


dfs(int idx, int cnt) {
        if (idx >= N) {
            maxCnt = Math.max(maxCnt, cnt);
            return;
        }

        if (line[idx] == 'P') {
            boolean matched = false;
            for (int jump = -K; jump <= K; jump++) {
                int target = idx + jump;
                if (target < 0 || target > N-1) continue;
                if (line[target] == 'H' && !eaten[target]) {
                    // 먹기
                    eaten[target] = true;
                    dfs(idx + 1, cnt + 1);
                    eaten[target] = false;
                    matched = true;
                }
            }
            if (!matched) dfs(idx + 1, cnt); // 못 먹고 넘어감
        } else {
            dfs(idx + 1, cnt); // 사람이 아닌 경우 그냥 넘어감
        }
    }

 

는 시간초과가 난다. 백트래킹이고. 그리디도 시간복잡도는 O(20000*20)로 똑같을 것 같은데 아니었다. 

코드 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        String line = sc.next();

        char[] arr = line.toCharArray();
        boolean[] eaten = new boolean[N];

        int count = 0;

        for (int i = 0; i < N; i++) {
            if (arr[i] == 'P') {
                // 앞뒤로 k칸 범위 탐색
                for (int j = i - K; j <= i + K; j++) {
                    if (j < 0 || j >= N) continue;
                    if (arr[j] == 'H' && !eaten[j]) {
                        eaten[j] = true;
                        count++;
                        break; // 한 사람은 햄버거 하나만 먹음
                    }
                }
            }
        }

        System.out.println(count);
    }
}

배우게 된 점

백트래킹은 시간복잡도가 더 작을 줄 알았는데.. 아니었다. 20개의 문자에 대해 K개의 선택을 하니까 20^K로 계산해야 한다. 

질문