[Python 3] BOJ 28467: Spell Cards

오늘의 문제는 Spell Cards 라는 문제이다.

 

https://www.acmicpc.net/problem/28467

28467번: Spell Cards

 

 

이 문제는 두 가지 방법으로 풀 수 있다고 한다.

 

Greedy Algorithm과 DP인데, 우선 내가 풀이한 방법은 Greedy Algorithm을 풀었다.

사실, DP 풀이법은 정확하게 모르겠고, 추가적으로 알게 되면 밑에 수정해서 추가하겠다.

 

Greedy Algorithm을 이용한 풀이는 생각보다 되게 naive하다.

매번 수들을 뒤져가면서 제일 작은 값을 가진 수를 찾는다. 그리고 제일 작은 값을 가진 수를 양옆에 있는 수들 중 한 개를 골라서, 합치는 식으로 한 개가 될 때까지 합친다.

 

제일 작은 값을 가진 수가 1개 이상인 경우도 있다. 이런 경우에는, 양 옆에 작은 수가 더 작은 숫자로 선정한다.

 

n=int(input())
data=[1e10]+list(map(int,input().split()))+[1e10]
answer=0
while len(data)!=3:
    temp=0
    minval=1e10
    side=1e10
    lr=0
    for i in range(len(data)):
        if data[i]<minval:
            temp=i
            minval=data[i]
            if data[i-1]<data[i+1]:
                side=data[i-1]
                lr=0
            else:
                side=data[i+1]
                lr=1
        if data[i]==minval:
            if min(data[i-1],data[i+1])<side:
                temp=i
                minval=data[i]
                if data[i-1]<data[i+1]:
                    side=data[i-1]
                    lr=0
                else:
                    side=data[i+1]
                    lr=1
    answer+=(minval+side)
    if lr==0:
        data=data[:temp-1]+[side]+data[temp+1:]
    else:
        data=data[:temp]+[side]+data[temp+2:]
print(answer)

 

해당 data를 받을 때, 왜 양 옆에 [1e10]을 붙혔는지 궁금할 것이다.

만약 첫번째 인덱스나 마지막 인덱스 중 한 개가 제일 작은 값을 가지고 있다고 하면, 이런 경우에는 인덱스 밖에 있는 숫자를 탐색해야할 수도 있으므로 따로 예외처리를 해주어야한다.

그런 불편함을 줄이기 위해서 양 옆에 매우 큰 숫자를 붙혀서, 만약 탐색하게 해도 선택되지 않도록 하였고, 내가 추가적으로 두 개의 숫자를 임의로 선정하였으므로, data의 크기가 "3"일때까지 탐색하는 방식을 사용하였다.

 

또한 lr은 leftright의 준말로 선정하여서, 제일 작은 숫자 옆에, 양 옆에 있는 작은 숫자가 왼쪽에 위치해있는지, 오른족에 위치해있는지 선택해주는 역할을 하는 변수이다.