문제
수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.
각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.
뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.
첫 번째로 공격받는 SCV는 체력 9를 잃는다.
두 번째로 공격받는 SCV는 체력 3을 잃는다.
세 번째로 공격받는 SCV는 체력 1을 잃는다.
SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.
남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.
예제
예제 입력 1
3
12 10 4
예제 출력 1
2
예제 입력 2
3
54 18 6
예제 출력 2
6
풀이
문제 분석
SCV의 갯수에 대한 입력의 크기는 N이며, 입력의 크기와 강하게 연관된 규칙은 각 SCV에게 9, 3, 1의 공격을 가하는 것이다. 공격의 경우의 수는 N (N-1) (N-2)로, nPr(이때 r은 n-3)의 가짓수를 가지며 SCV는 최대 3기까지 존재가능하므로 N=3 이다. 따라서 한번의 공격 회차에서 최대 3P0 = 3!의 경우의 수가 존재한다.
어떻게 접근해야 할까?
사실 다이나믹 프로그래밍 공부하려고 골라서 dp방식으로 풀 수 있다는 건 알고 있다. 어떻게 접근해야 다이나믹 프로그래밍까지 도달할 수 있는지 알아보자...
그리디 알고리즘을 이용한 접근
가장 간단한 그리디 알고리즘에 대해 생각해보았다. 예제 입력1과 같이 정렬된 상태에서 큰 숫자부터 높은 공격을 가하는 방식인데, 이 경우 당연하게도 최적해를 만들지 못한다. 즉 적절하게 값을 분배하지 못할 가능성이 크다.
여기서 적절하게 값을 분배하는 것에 대해 생각해보자. SCV 한 기의 체력에 대해 9, 3, 1 중 하나를 이용해 0 이하로 만들어야 한다면 무조건 9만 사용하는 것이 이득일 것이다. 조금 더 범위를 넓혀 다른 SCV까지 생각한다면 9를 굳이 사용할 필요가 없다면 낮은 숫자를 사용해야 이득일 것이다.(다른 SCV도 9를 써야 하니까...) 이 경우 거스름돈 문제와 유사하다. 다행히도 뮤탈리스크의 공격력은 배수 관계를 가지므로 그리디 알고리즘으로 해결할 수 있다!
SCV 각각에 대한 그리디 알고리즘으로 적절한 공격 횟수를 찾게 되었다면 모든 SCV의 공격횟수를 비교해 최솟값을 찾을 수 있지 않을까? 라는 가설을 세워보았다.
그런데 이 방식을 사용할 시 한 기의 SCV 체력이 0으로 맞아떨어지는 공격횟수를 구하는 것과, 한 번의 공격에서 9, 3, 1을 각각 한번씩만 사용해야 한다는 규칙때문에 이를 비교하는 과정이 복잡하기 때문에 코드가 난잡해지고 원하는 결과가 나오지 않을 가능성이 클 거 같아 포기했다.
완전 탐색 브루트-포쓰
머리가 안 굴러가서 알고리즘 분류로 힌트를 한번 들춰봤다. 확인해보니 그래프 이론과 탐색이 있어 조금 더 생각해보니 큐에 SCV의 상태를 넣고 SCV의 상태에 따라 최대 6가지의 공격방식을 넣게 된다면 해결 가능할 것이라고 생각했다. (1로 60번 공격할리는 없으니까 시행횟수가 6*60보다 낮지 않을까??)
원래 생각한 다이나믹 프로그래밍과는 동떨어져 있지만 해당 방법으로 풀이를 해보았다.
입력의 길이가 짧아서 뇌를 빼고 공격방식을 생각해봤다. SCV 갯수에 따라 6, 2, 1 총합 9가지이므로 리스트에 저장해두고 비트 연산으로 범위를 지정해주면 순열을 안쓰지 않을???까??? 좀 더 일반적인 방식은 나중에 생각해보도록 하자....
from collections import deque
def bfs():
q = deque()
q.append([scv, 0])
start = [0,1,3]
end = [1,3,8]
while q:
current, cnt = q.popleft()
# print(current)
length = len(current) # 1, 2, 3
if length == 0: return cnt
cnt += 1
# attack 범위는 0:1, 1:3, 3:8 이다.
# 무지성으로 때려박는다.
for i in range(start[length-1], end[length-1]):
temp = current[:]
for j in range(length):
temp[j] -= attack[i][j]
q.append([[temp[k] for k in range(length) if temp[k] > 0], cnt])
attack = [1], [1, 3], [3, 1], [1, 3, 9], [1, 9, 3], [3, 1, 9], [3, 9, 1], [9, 1, 3], [9, 3, 1]
n = int(input())
scv = list(map(int, input().split()))
print(bfs())다음과 같이, 무작정 때려박는 개멍청한나이브한 풀이를 시도해보았다. BFS를 이용했으니 가장 먼저 나오는 것이 최단거리(최적해)일 거란 무식한 방안에서 착안한 방식으로...
당연히 실패했다.
그렇게 콘솔창을 유심히 살펴보다가 생각이 하나 떠올랐는데...
다음과 같이 중복되는 케이스가 있는 경우, 순서가 없으므로 같은 경우이니 해당 계산을 생략하면 오버헤드도 줄이고 메모리 사용률도 줄이지 않을까!!! 라는 생각에 드디어 도달하게 된 것이다!
그래서 이제 뭐함?
DP에 매몰되서 헤매다가 결국 구글링 해보았다.
알고보니 체력에 대한 정보를 메모이제이션하여 BFS를 최적화하는 문제였다.
따라서 BFS에 더 가까운 문제라고 한다.
참고자료
해결방법을 알았으니 구현해보자.
딕셔너리에 SCV의 체력 정보를 튜플 키로 등록해 메모이제이션하여 공격 횟수를 기록한다.
만약 공격횟수가 크다면 While문의 해당 루프를 continue문으로 생략한다.
from collections import deque
def bfs():
q = deque()
q.append([scv, 0])
memoi = dict()
memoi[tuple(scv)] = 0 # tuple memoization
while q:
current, cnt = q.popleft()
# print(current)
if current == [0,0,0]: return cnt
if memoi[tuple(current)] and memoi[tuple(current)] < cnt: continue # 이미 있을 경우
cnt += 1
for i in range(6): # 공격의 경우의 수
temp = current[:]
for j in range(3): # 공격 순서
temp[j] -= attack[i][j]
for j in range(3): # 음수는 0으로 만들기
if temp[j] < 0: temp[j] = 0
temp.sort() #정렬
q.append([temp, cnt])
memoi[tuple(temp)] = cnt
attack = [1, 3, 9], [1, 9, 3], [3, 1, 9], [3, 9, 1], [9, 1, 3], [9, 3, 1]
n = int(input())
scv = list(map(int, input().split()))
if len(scv) < 3: scv + [0]*(3-len(scv))
print(bfs())
응 시간초과
왜 시간초과가 생겼나 했더니 문제점이 있었다.
cnt를 비교하는 논리연산자가 <여서 같은 횟수에 대해서도 루프문이 돌아간다는 것이 있었고...
추가로 scv가 두기 이하일 시 인덱스 에러가 생기는 문제가 있었다. += 연산자 써야하는데 대입연산자(=)를 까먹었다...!
수정한 코드는 다음과 같다.
for문 안에서 if문을 작성하면 오버헤드가 줄어들 지 않을까 해서 코드 위치도 옮겨보았다.
아마 별 차이는 없을 것으로 예상된다.
from collections import deque
def bfs():
q = deque()
q.append([scv, 0])
memoi = dict()
memoi[tuple(scv)] = 0 # tuple memoization
while q:
current, cnt = q.popleft()
# print(current)
if current == [0,0,0]: return cnt
cnt += 1
for i in range(6): # 공격의 경우의 수
temp = current[:]
for j in range(3): # 공격 순서
temp[j] -= attack[i][j]
for j in range(3): # 음수는 0으로 만들기
if temp[j] < 0: temp[j] = 0
temp.sort() #정렬
if tuple(temp) in memoi and memoi[tuple(temp)] <= cnt: continue
q.append([temp, cnt])
memoi[tuple(temp)] = cnt
attack = [1, 3, 9], [1, 9, 3], [3, 1, 9], [3, 9, 1], [9, 1, 3], [9, 3, 1]
n = int(input())
scv = list(map(int, input().split()))
if len(scv) < 3: scv += [0]*(3-len(scv))
print(bfs())
