728x90
반응형
문제:
기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 이하인 햄버거를 먹을 수 있다.
| 햄버거 | 사람 | 햄버거 | 사람 | 햄버거 | 사람 | 햄버거 | 햄버거 | 사람 | 사람 | 햄버거 | 사람 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
위의 상태에서 인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.
- 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
- 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
- 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
- 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
- 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
- 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음
인 경우에는 6명 모두가 햄버거를 먹을 수 있다.
- 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
- 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
- 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
- 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
- 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
- 12번 위치에 있는 사람: 11번 위치에 있는 햄버거
식탁의 길이 , 햄버거를 선택할 수 있는 거리 , 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.
입력:
첫 줄에 두 정수 과 가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 인 문자열로 주어진다.
출력:
첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다
풀이방법:
사람을 기준으로 -K인 인덱스부터 햄버거를 우선 배정하는 그리디 알고리즘을 사용한다. 인덱스를 사용하기 때문에 IndexError가 발생하지 않도록 주의한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
N, K = map(int, input().split())
burger = list(input())
answer = 0
for i in range(len(burger)):
if burger[i]=='P':
idx = i-K
if idx<0:
idx=0
while idx>=0 and idx<=i+K and idx < N:
if burger[idx]=='H':
burger[idx]=''
answer+=1
break
idx+=1
print(answer)
|
cs |
문제링크:
https://www.acmicpc.net/problem/19941
19941번: 햄버거 분배
기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사
www.acmicpc.net
728x90
반응형
'Algorithm > Python' 카테고리의 다른 글
| [BOJ] 1515. 수 이어 쓰기 (0) | 2023.07.24 |
|---|---|
| [Programmers] Lv 2. 무인도 여행 (0) | 2023.07.21 |
| [BOJ] 20920. 영단어 암기는 괴로워 (0) | 2023.07.19 |
| [Programmers] Lv 2. 연속된 부분 수열의 합 (0) | 2023.07.18 |
| [BOJ] 21921. 블로그 (0) | 2023.07.17 |