[Greedy] 12931번 두 배 더하기

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

알고리즘

• Greedy

풀이

포인트

• BFS나 Brute Force 풀면 시간초과가 뜬다.
• greedy한 접근법을 통해 풀이 시간을 줄여야한다.

BFS

딕셔너리 visited를 key 상태까지 도달하기 위한 최소 연산 횟수로 정의한다.
그리고 큐에서 현재 상태를 꺼낼 때마다, n개의 원소에 대해, i번째 원소에 1을 더한 a의 새로운 상태를 큐에 넣는다.
또한, 일괄적으로 2배를 한 a의 새로운 상태도 큐에 넣는다.

이 풀이의 시간 복잡도는 어떻게 될까?
최악의 경우, 길이가 50이면서 b의 모든 원소는 1000의 값을 가진다. 0에서 1000까지 1씩 더하면 1000번의 계산이 필요하므로, 대략 시간복잡도는 $O(50 \times 1000 \times 1000) \approx O(10^8)$. 아슬아슬할 줄 알았는데 시간초과가 뜬다. 아마도 시간 복잡도 계산이 잘못됐을 수도 있을 것 같다.

BFS 소스코드는 아래와 같다.

[Source Code]

from collections import deque
n = int(input())
b = list(map(int,input().split()))
a = [0]*n
def key(l):
    return ' '.join(map(str,l))
def unkey(l):
    return list(map(int,l.split(' ')))
visited = {}
q = deque()
k = key(a)
visited[k] = 0
q.append(k)
while q:
    k = q.popleft()
    unk = unkey(k)
    if k == key(b):
        print(visited[k])
        break
    for i in range(n):
        unk[i] += 1
        tmp = key(unk)
        if visited.get(tmp) is None:
            visited[tmp] = visited[k]+1
            q.append(tmp)
        unk[i] -= 1
    unk = [i*2 for i in unk]
    tmp = key(unk)
    if visited.get(tmp) is None:
        visited[tmp] = visited[k]+1
        q.append(tmp)

Greedy

그리디하게 생각해보면, 최소 연산 횟수를 구하라고 했으니, 1을 더하는 것보다는 두 배를 하는 것이 훨씬 빠르다. 단, 거꾸로 배열 b에서 배열 a로 가는 방법을 생각해보자. 그러면 아래와 같은 pseudo code를 생각해볼 수 있다.

• b 배열의 모든 원소가 2로 나누어 떨어지는지 확인한다.
  • 나누어 떨어진다면, 모든 원소를 2로 나누는 것이 최소 연산 횟수를 구하는 그리디 방법이다.
  • 나누어 떨어지지 않는다면, 나누어 떨어지지 않는 하나의 원소에서 1을 뺀다. 반복하다보면 모든 원소가 2로 나누어 떨어지는 때가 온다.
    위와 같은 접근법이 유효한 이유는, 2로 나누는 것이 1로 나누는 것보다 더 적은 연산 횟수를 보장하기 때문이다.

n = int(input())
b = list(map(int,input().split()))
a = [0]*n
ans = 0
def check(l):
    for i in range(len(l)):
        if l[i] != 0:
            return True
    return False
while check(b):
    cnt = 0
    index = -1
    for i in range(n):
        if b[i]%2 == 0:
            cnt += 1
        else:
            if index == -1:
                index = i
    if cnt == n:
        for i in range(n):
            b[i] /= 2
    else:
        b[index] -= 1
    ans += 1
print(ans)