[백준/ 파이썬] 12931번 두 배 더하기

백준 12931번 두 배 더하기

문제를 요약해보겠습니다.
아래 조건을 가지고 0으로 채워진 배열을 입력된 배열로 바꾸는 문제입니다.

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

0으로 채워진 배열을 A, 주어진 배열을 B라고 한다면. A->B로 가는 최적의 경우는 아마 찾기 힘들고 모든 경우에 대해서도 성립할지가 의문입니다.
따라서 B->A로 가는 과정을 살펴볼것입니다. 이 경우가 최적의 해를 보장해주겠네요.

주어진 배열 B로 부터 A를 만드는 것이 목표

그렇다면 어떻게 코드를 짜면 좋을까요?

배열 B를 반복문을 통해 찾아보면서 그 값이 홀수라면 -1을, 짝수라면 가만히 두었다가 2로 나눌때 나눠주면 되겠습니다.
즉, 홀수인 친구들을 짝수로 만드는것이 중요합니다. 왜냐하면 최대한 2로 나누는것이 좋으니까요.

제가 처음에 실수를 했던 부분이 있는데, 그 부분은 배열B의 요소가 하나라도 2로 나누어 떨어지지 않을때 모두에게 1을 빼주는 생각을 해주었습니다. 왜 그렇게 풀었는지 잘 모르겠네요.

1은 부분적으로 뺄 수 있기때문에 먼저 홀수를 짝수로 만들어주는것입니다.

따라서 규칙을 생각해보면 다음과 같습니다.

1. 홀수라면 1을 뺴주자
2. 홀수일때 1을 빼줬으니까 다음번에는 2로 나누기로 하자. 그런데 이제 0이나 1이 있을때라면 2를 나눠줄수 없으니 판단해주도록 합니다.

n = int(input())
arr = list(int(x) for x in input().split())
arr.sort()

cnt = 0

while sum(arr) != 0:
    check = 0
    for i in range(n):
        if arr[i] % 2 != 0 or arr[i] == 0 or arr[i] == 1:
            if arr[i] == 0:
                continue
            else:
                arr[i] -=1
                cnt += 1
            check = 1
    if check == 0:
        for i in range(n):
            arr[i] //= 2
        cnt += 1

print(cnt)