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

문제

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

12931번: 두 배 더하기

백준 12931번 두 배 더하기

처음 문제를 읽고 BFS로 풀면 될 것 같았다.

 

그래서 BFS로 구현을 시도해 봤는데 아무리 생각해도 연산량이 너무 많은 것 같아 불안했는데, 역시나 메모리 초과를 받았다.

 

그래서 문제 분류를 확인했는데, 그리디 문제였다.

 

이게 그리디?라는 의문을 가지고 연습장에 끄적끄적하다 보니 생각보단 빠르게 규칙을 찾을 수 있었다.

 

모든 값이 0으로 채워져 있는 길이가 N인 배열 A부터 시작하는 것이 아닌, 반대로 배열 B에서 0으로 만들어 가면 그리디로 쉽게 풀 수 있었다.

 

반대로 생각해 보면,

배열의 모든 요소가 짝수라면 모든 요소에 나누기 2해 주고, 하나라도 홀수가 있다면 그 요소만 -1해 주면 쉽게 풀 수 있는 문제였다.

 

어쩐지 정답률이 높다 싶었다.

 

정답

n = int(input())
B = list(map(int, input().split()))
count = 0
while sum(B) != 0 :
    for i in range(n) :
        if B[i] % 2 == 1 :
            B[i] -= 1
            break
    else :
        B = list(map(lambda x:x//2, B))
    count += 1
print(count)