컴굥일지
[BOJ/백준 19941][C++] 햄버거 분배 본문
반응형
문제
https://www.acmicpc.net/problem/19941
문제 내용
햄버거 H와 사람 P의 순서가 표시된 문자열이 주어진다.
사람은 자기 주변으로 k만큼 거리 안에 있는 햄버거만 먹을 수 있다.
최대한 많은 사람이 햄버거를 먹을 수 있도록 할 때, 최대 사람 수를 구하면 된다.
문제 풀이
greedy한 문제이다.
사람을 기준으로 (-k~k) 범위 안에 있는 햄버거 중 가장 좌측에 있는 것을 먹도록 하면 된다.
햄버거를 먹으면 그 배열의 원소를 H나 P가 아닌 문자로 바꾸고 계속 탐색을 진행하면 된다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//입력
int n, k;
cin >> n >> k;
vector<char>arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
//문제 해결
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 'P') {
for (int j = i - k; j <= i + k; j++) {
//배열 범위 밖으로 나가는 것 방지
if (j<0 || j>n - 1) continue;
if (arr[j] == 'H') {
count++;
arr[j] = 'Q'; //H,P이외의 문자로 변경
break;
}
}
}
}
cout << count << '\n';
}
반응형
'알고리즘 > 코테 문제' 카테고리의 다른 글
[BOJ/백준 18115][C++] 카드 놓기 (0) | 2022.03.15 |
---|---|
[BOJ/백준 14713][C++] 앵무새 (0) | 2022.03.14 |
[BOJ/백준 11501][C++] 주식 (0) | 2022.03.10 |
[BOJ/백준 13413][C++] 오셀로 재배치 (0) | 2022.03.09 |
[BOJ/백준 9237][C++] 이장님 초대 (0) | 2022.03.08 |
Comments