C언어 4차시 Layer7 과제 - 백준 19941

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;

char str[20001];
int n, k, cnt, found, s1, i, j;

int main() {
    scanf("%d %d", &n, &k);
    scanf("%s", str);
    for (i = 0; i < n; i++) {
        if (str[i] == 'P') {
            found = 0, s1 = i - k < 0 ? 0 : i - k;
            for (; s1 < i ; s1++)
                if (str[s1] == 'H' && str[s1]>1) {
                    str[s1] = 1;
                    cnt++;
                    found = 1;
                    break;
        }
    if (!found)
        for(j=i+1;j<n&&j<=i+k;j++)
            if (str[j] == 'H'&&str[j]>1) {
                str[j] = 1;
                cnt++;
                break;
            }
        }
    }
    printf("%d", cnt);
}

---

· 이 문제의 분류는 그리디 알고리즘이다. 최적의 경우를 골라내는 건데 그리디 알고리즘을 사용하는 이유를 생각해봤더니, 사람의 최대한 왼쪽에 있는 햄버거를 선택하면 언제나 최적의 경우의 수가 나온다는 것을 알게 되었다.

· 일단 입력받은 배열의 맨 처음부터 맨 끝까지 탐색을 한다. 그러다가 탐색중인 배열의 값이 'P'인 경우가 생기면 i-k부터 i+k까지 루프를 돌며 그 중 가장 먼저 나오는(가장 왼쪽에 있는) 'H'를 취하고(count값 증가), 그 배열값은 의미없는 값으로 바꾼다. 이 과정을 반복하면 매번 최적의 상황만 골라져서 나오기 때문에 쉽게 해결할 수 있다.

· 참고로 그리디 알고리즘을 사용할 수 있는 경우는 극히 제한적이므로 이렇게 언제나 한 가지 상황만 보고 최적의 상황을 계산해낼 수 있는 상황에서만 사용하고 그렇지 않은 경우에서는 Dynamic Programming 알고리즘을 사용해야 한다.