Python 29제] 2020년 한국정보올림피아드 1차대회 중등부 2교시 1번:햄버거 분배

문제]

기다린 벤치 모양의 식탁에 사람들과 햄버거가 아래 그림과 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 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가 나온다. (1≤N≤20,000, 1≤k≤10) 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.

 

출력 형식

여러분은 첫 줄에 하나의 정수를 출력한다. 이 수는 입력에 대해서 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

 

 

입력/출력 예시]

입력1

20 1

HHPHPPHHPPHPPPHPHPHP

 

출력1

8

 

입력2

20 2

HHHHHPPPPPHPHPHPHHHP

 

출력2

7

 

 

 

출처 : 한국정보올림피아드(2020년도 한국정보올림피아드 1차 대회 중등부 2교시 문제)

 

 

 

참고풀이]

import sys #exit()

#자료를 입력받아 입력형식에 맞게 자료가 입력되었는 지 체크한다.
N,k=map(int,input().split())
if 1<=N<=20000 and 1<=k<=10:
    HP=input()
    for hp in HP:
        if hp=='P' or hp=='H':
            continue
        else:
            sys.exit()

    #조건에 맞게 처리한다.
    count=0
    j=0
    for i in range(N):
        if HP[i]=='P':
            continue
        else:
            for j in range(max(j,i-k),min(N,i+k+1)):
                if HP[j]=='H':
                    continue
                else:
                    count+=1
                    j+=1
                    break
    #결과출력
    print(count)

 

 

참고풀이 결과]

 

 

 

대한민국의 아름다운 영토, 독도의 봄