19941번 : 햄버거 분배

https://www.acmicpc.net/problem/19941

19941번: 햄버거 분배

 

 

문제

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        String[] s =  br.readLine().split("");
        int count=0;
        for(int i=0;i<n;i++) {
            if(s[i].equals("P")) {
                for(int j=Math.max(0,i-k);j<=Math.min(n-1, i+k);j++) {
                    if(s[j].equals("H")) {
                        s[j]="O"; count++; break;
                    }
                }
            }
        }
        bw.write(count+""); bw.flush();
    }
}

 

 

해결방법

이중 반복문을 쓰면 시간 초과가 날 것 같아 다른 방법을 고민해봤는데 딱히 떠오르지 않아서 그냥 이중 반복문을 사용하였다.

단순히 위치가 'P'일 때 선택할 수 있는 거리에 햄버거가 있다면 결과값을 증가시키면 된다.

이때, 'P'를 기준으로 왼편에 있는 햄버거는 가장 먼 햄버거를 택해야하고 오른편에 있는 햄버거는 가장 가까운 햄버거를 택해야 한다. 그래야 햄버거를 먹을 수 있는 최대 사람 수를 구할 수 있다. 이유는 조금만 생각해보면 이해될 것이다.

이를 코드로 구현하면 해결된다. 시간초과가 날 줄 알았는데 통과했다. 다른 사람들의 코드도 보았는데 대부분 이중 반복문을 사용하였다. 

 

햄버거를 택할 때 왼편 먼 곳, 오른편 먼 곳을 택한 다면 아래 테스트 케이스에서 결과가 정상적으로 나오지 않는다.

6 2
PHHHPP

=> 3이 나와야하는데, 2가 나온다.