정보올림피아드 (햄버거 문제)

개요

안녕하세요. 

학원생 중 정보올림피아드 대회를 준비하는 심화반 학생이 있어 같이 풀어본 문제입니다.

먼저 문제를 살펴보겠습니다.

[출처 : 한국정보올림피아드, 2020년 중등부 2교시 문제]

 

예를 들어 입력이 아래와 같다면,

12 1

HPHPHPHHPPHP

출력은 아래와 같아야 합니다.

5

 

K가 2 라면 (햄거버를 먹을 수 있는 거리),

12 2

HPHPHPHHPPHP

출력은 아래와 같아야 합니다.

6

문제풀이

1. 왼쪽부터 HPHPHP... 을 진행하며 P(사람)을 검색.

2. 사람(P)을 찾은 경우, 사람인덱스 기준 -K~+K 까지 햄버거 검색.

3. 햄버거가 있다면 (H를 만나면) 먹고, 햄버거 위치에 먹었다는 표시. (예, 'X')

4. 햄버거를 먹었다는 표시를 하는 이유는, 다음 P(사람)이 이미 먹은 햄버거를 또 먹는 것을 방지. 

5. 전체적으로 테이블(HPHPHP...)을 반복하는 루프와 테이블 내 사람(P)를 만났을때 -K~+K를 반복하는 이중 루프로 구현.

6. 단, 테이블의 왼쪽에 사람이 있는 경우 -K가 0보다 작은 경우, 테이블의 오른쪽 끝에 사람이 있는 경우, +K가 테이블의 길이를 초과하는 경우를 주의.

[햄버거 분배문제 해결 알고리즘]

 

소스코드 (파이썬)

x = input('식탁길이, 선택거리:')
y = input('햄버거, 사람 배치(H, P):')

xx = x.split(' ')
#n:식탁길이, k:거리
n = int(xx[0])
k = int(xx[1])

yy = list(y)

p = 0        
for i in range(n):
    if yy[i] == 'P':
        if i-k<0:
            start = 0
        else:
            start = i-k

        if i+k+1>n:
            end = n
        else:
            end = i+k+1

        for j in range(start, end):
            if yy[j] == 'H':
                p += 1
                yy[j] = 'X'
                break

print(p)

[파이썬 출력]

소스코드 (C++)

#include <iostream>
#include <string>

int main()
{
	int n, k;
	std::cin >> n >> k;

	std::string s;
	std::cin >> s;
	
	int p = 0;
	int start = 0, end = 0;
	for (int i = 0; i < n; i++)
	{
		if (s[i] == 'P')
		{
			if (i - k < 0)
				start = 0;
			else
				start = i - k;

			if (i + k + 1 > n)
				end = n;
			else
				end = i + k + 1;

			for (int j = start; j < end; j++)
			{
				if (s[j] == 'H')
				{
					p += 1;
					s[j] = 'X';
					break;
				}
			}
		}
	}

	std::cout << p << '\n';
}

[C++ 출력]

 

파이썬, C++ 둘 다 결과는 같습니다.

감사합니다.