문제
현대자동차그룹은 주요 물류센터에 각종 자동화 기기를 도입하며 ‘스마트 물류’를 실현하고 있다.
최근에는 자동차 반조립 부품(KD, Knock-Down) 물류기지인 KD센터에 포장 관련 자동화 로봇 개발과 구축을 완료했다.
기존 수작업으로 진행하던 일부 작업 라인을 자동화 기기로 전환해 생산성을 높이기 위한 시도다.
기다란 작업 라인에 로봇과 부품이 아래 그림과 같이 단위 간격으로 놓여 있다. 로봇들의 위치에서 거리가 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
Plain Text
복사
출력
8
Plain Text
복사
예시2
입력
20 2
HHHHHPPPPPHPHPHPHHHP
Plain Text
복사
출력
7
Plain Text
복사
정답
import sys
N, K = list(map(int, sys.stdin.readline().split()))
work_line = list(sys.stdin.readline())
answer = 0 # 부품을 잡은 로봇의 수
for i in range(N):
if work_line[i] == 'P': # P가 나오면 잡을 수 있는 부품 확인
for j in range(i-K, i+K+1): # 왼쪽에서부터 확인한다.
if (j < 0) or (j >= N): continue # 범위를 넘으면 pass
if work_line[j] == 'H': # 만약 잡을 수 있는 부품이 있다면
work_line[j] = 'C' # 해당 부품은 잡았다고 표시하고
answer += 1 # 부품을 잡은 로봇 수 + 1
break
print(answer)
Python
복사
풀이
•
Greedy 방법으로 풀 수 있다.
•
step은 다음과 같다.
1.
왼쪽부터 로봇을 하나씩 살펴본다.
2.
로봇 기준으로 왼쪽에서부터 K 이내에 부품이 존재하는 경우 부품을 집는다.
3.
만약 부품을 잡는 경우 잡은 부품은 잡혔다고 표시하고 부품을 잡은 로봇수를 +1한다.
* 왜 왼쪽에서부터 훑으면 가능한건지는 사실 잘 모르겠다..
answer = 0 # 부품을 잡은 로봇의 수
for i in range(N):
if work_line[i] == 'P': # P가 나오면 잡을 수 있는 부품 확인
for j in range(i-K, i+K+1): # 왼쪽에서부터 확인한다.
if (j < 0) or (j >= N): continue # 범위를 넘으면 pass
if work_line[j] == 'H': # 만약 잡을 수 있는 부품이 있다면
work_line[j] = 'C' # 해당 부품은 잡았다고 표시하고
answer += 1 # 부품을 잡은 로봇 수 + 1
break
print(answer)
Python
복사