[ BOJ ] 12931 : 두 배 더하기 ( GOLD 5 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/12931)

문제

모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다.

• 배열에 있는 값 하나를 1 증가시킨다.
• 배열에 있는 모든 값을 두 배 시킨다.

배열 B가 주어졌을 때, 배열 A를 B로 만들기 위한 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N이 주어진다. (1 ≤ N ≤ 50)

둘째 줄에는 배열 B에 들어있는 원소가 공백으로 구분해서 주어진다. 배열에 B에 들어있는 값은 0보다 크거나 같고, 1,000보다 작거나 같다.

출력

첫째 줄에 배열 A를 B로 바꾸기 위한 최소 연산 횟수를 출력한다.

풀이 과정

배열의 원소마다 각각 2로 나눠지는 횟수, 2의 거듭제곱으로 나눠지고 난 나머지 수를 구하였다.

예를 들어, 입력 배열의 원소가 1 2 6 9 일 경우

1 -> (0, 1) 0 -> (+1) 1

2 -> (1, 1) 0 -> (+1) 1 -> (x2) 2

6 -> (2, 2) 0 -> (+1) 1 -> (x2) 2 -> (+1) 3 -> (x2) 6

9 -> (3, 2) 0 -> (+1) 1 -> (x2) 2 -> (x2) 4 -> (x2) 8 -> (+1) 9

를 구한다.

 

배열에 있는 모든 값을 두 배 시키는 연산의 횟수를 줄이기 위해선 큰 수부터 차례대로 ( 작은 수가 같이 2배가 되면 안되니 ) , 그리고 될 수 있을 때 한번에 많은 원소를 두 배 시키는 것이 좋다.

 

두 배 연산을 최대한 뭉쳐서 수행할 수 있도록 연산의 순서를 정하면 다음과 같다.

1 -> (0, 1) 0 ->                                                                                                         (+1) 1

2 -> (1, 1) 0 ->                                                            (+1) 1 ->                (x2) 2

6 -> (2, 2) 0 ->                               (+1) 1 -> (x2) 2 ->                (+1) 3 -> (x2) 6

9 -> (3, 2) 0 -> (+1) 1 -> (x2) 2 ->                (x2) 4 ->                               (x2) 8 ->             (+1) 9

                          1             2             3            4             5              6             7            8          9

 

따라서, (배열의 원소들이 각각 2로 나눠지는 횟수 중 최댓값) + (배열의 원소들이 2의 거듭제곱으로 나눠지고 난 나머지 수 합) 이 정답이 된다.

 

import sys
from collections import deque
input = sys.stdin.readline

n = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))

cnt = [[0, 0] for _ in range(n)]
for i in range(n):
    while arr[i] > 0:
        if arr[i] % 2 == 0: 
            arr[i] //= 2
            cnt[i][0] += 1
        else: 
            arr[i] -= 1
            cnt[i][1] += 1
print(cnt)
max_value = cnt[0][0]
sum_value = cnt[0][1]
for i in range(1, n):
    max_value = max(cnt[i][0], max_value)
    sum_value += cnt[i][1]
print(max_value + sum_value)