[백준] 19941번 : 햄버거 분배 (파이썬)

그리디 알고리즘 문제

 

ex)

input 

12 2
HPHPHPHHPPHP

output 

6

 

(1) 처음 내 코드 (실패)

a,b=map(int,input().split())
ham = list(input()) # H P
cnt=0

for i in range(len(ham)):
    if ham[i]=="P":
        change=False
        for j in range(i-b,i,1):
            if j<0 or j>=a:
                continue
            else:
                if ham[j]=="H":
                    ham[j]="O"
                    change=True
                    cnt+=1
                    break
        if change==False:
            for j in range(i+b,i,-1):
                if j<0 or j>=a:
                    continue
                else:
                    if ham[j]=="H":
                        ham[j]="O"
                        change=True
                        cnt+=1
                        break
        

print(cnt)

list 값이 "P"라면 양옆에 값을 모두 확인해가면서 "H"를 찾아야 한다. 그리고, 한번 사용된 "H"는 다시 사용되면 안되므로 이 값을 다른 값으로 바꿔주어야 한다. 한 번 쓰인 햄버거는 이미 썼다는 뜻을 담아 "O"의 값을 갖도록 바꿔주었다.

처음 내 코드는 사용하지 않은 햄버거라면 가능한 가장 먼 거리의 햄버거부터 사용하도록 코드를 짰다. 또, "P"의 왼쪽 값부터 확인하여 "P"의 왼쪽에서 햄버거를 찾는다면 그 값을 사용해주었고, 왼쪽에서 햄버거가 발견되지 않는다면 "P"의 오른쪽 값도 확인하여 햄버거를 사용하게끔 코드를 짜주었다. change라는 bool 변수를 두어, 왼쪽에서 햄버거를 찾아서 사용했는지 여부를 저장해주었다.

결론은 실패하였다. 반례가 될만 한 케이스들은 거의 모두 해봤는데, 어디가 정확히 문제인진 찾지 못했다. 뒤에 있는 "P"도 고려하며 햄버거를 사용하지 않은 것이 문제일까? 아무튼 정확한 이유는 찾지 못했다.

 

(2) 코드 수정 후 내 코드 (성공)

a,b=map(int,input().split())
ham = list(input()) # H P
cnt=0

for i in range(len(ham)):
    if ham[i]=="P":
        for j in range(i-b,i+b+1,1):
            if j<0 or j>=a:
                continue
            else:
                if ham[j]=="H":
                    ham[j]="O"
                    cnt+=1
                    break
print(cnt)

일단, 위의 (1)번 코드에서 불필요하게 case를 두개로 나누어 for문을 돌 필요가 없다는 생각이 들어, 코드 최적화를 진행해주었다. 그 후에 혹여나 하는 마음으로 재제출을 해보았는데, 성공하였다.