🧷 19941번 햄버거 분배
(문제 링크: https://www.acmicpc.net/problem/19941)
🌸 문제
기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 K이하인 햄버거를 먹을 수 있다.
위의 상태에서 K = 1인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.
- 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
- 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
- 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
- 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
- 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
- 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음
K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.
- 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
- 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
- 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
- 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
- 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
- 12번 위치에 있는 사람: 11번 위치에 있는 햄버거
식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.
🌸 입력
첫 줄에 두 정수 N과 K가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.
🌸 출력
첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.
🌸 풀이
# 선택거리 K 이하의 왼쪽에 위치한 햄버거 먹기
import sys
input = sys.stdin.readline
N, K = map(int, input().split()) # 테이블 크기는 N, 선택 거리는 K 이하
string = input().rstrip() # P,H로 이루어진 길이가 N인 문자열
table_list = list(string)
count = 0
for i in range(len(table_list)):
if table_list[i] == "P":
for j in range(i-K, i+K+1): # 왼쪽으로 선택 거리 K 이내의 햄버거 확인하기
if 0 <= j < N and table_list[j] == "H": # 인덱스가 테이블 범위 내에 있고, 햄버거가 있는 경우
count += 1
table_list[j] = "E" # 먹은 햄버거
break
print(count)⌛ 시간복잡도
이 풀이의 시간복잡도는 O(NK)이다. 각 학생마다 왼쪽으로 선택 거리 K 이내에 있는 햄버거를 확인하기 위해 최대 K번의 반복이 필요하며, 이를 테이블의 모든 위치에 대해 반복하므로 N번의 반복이 추가된다. 효율적인 방법은 아니라는 소리..
📕 브루트포스(Brute Force)
브루트 포스(Brute Force) 방식은 가능한 모든 경우를 탐색하여 해를 찾는 방법. 이 방법은 각각의 가능성을 모두 시도해보고 그 중에서 정확한 해를 찾아내는 방식으로 작동한다. 일반적으로 브루트 포스 방식은 간단하고 직관적이며, 모든 가능성을 검사하기 때문에 정확한 해를 찾을 수 있지만 경우의 수가 많은 경우에는 실행 시간이 매우 오래 걸릴 수 있다.
앞선 코드에서 사용된 브루트 포스 방식은 각 학생에 대해 왼쪽으로 선택 거리 K 이내에 있는 햄버거를 확인하여 먹을 수 있는지 여부를 확인하는 것이다. 이를 위해 모든 학생에 대해 반복하고, 각 학생마다 왼쪽으로 선택 거리 K 이내에 있는 햄버거를 확인한다. 이 과정에서 모든 가능한 위치를 탐색하여 햄버거를 먹을 수 있는지 여부를 판단하므로 이 코드는 가능한 모든 경우를 탐색하여 해를 찾는 브루트 포스 방식으로 작동한다.
