BOJ 12931번: 두 배 더하기

www.acmicpc.net/problem/12931

12931번: 두 배 더하기

아이디어:

처음에는 A를 만들어서 B와 같게 만들려고 했는데, B=[100]인 경우를 어떻게 해결해야 할 지 찾지 못했다.

그러던 중 구글링을 통해, B의 원소를 모두 0으로 만드는 방식으로 접근해야 한다는 걸 찾았다.

 

1. B를 오름차순으로 정렬한다.

2. B의 모든 원소가 2로 나누어떨어지도록 세팅한다.

    B의 원소가 2로 나누어떨어지지 않는 경우, B[i]-- ans++

3. B의 모든 원소가 2로 나누어떨어지는 경우, 모든 B의 원소를 2로 나눈 후 ans++

 

실수:

B의 원소를 0으로 만드는 방식으로 접근해야 한다는 걸 생각하지 못했다.

B의 원소가 2로 나누어떨어진다고 모든 B의 원소가 2로 나누어떨어지는 것은 아니다. 이 경우를 생각하지 못했다.

모든 원소를 2로 나누는 게 하나의 시행인 것을 놓쳐서 for 문 안에 ans++를 했다.

B[i]-- 시행 후 B[i]가 0이 되면 나누는 연산을 시행하지 않는 부분을 놓쳤다.

 

코드:

import sys
n = int(sys.stdin.readline())
b = list(map(int, sys.stdin.readline().split()))
ans = 0
b.sort()      
for j in range(n):
    if (b[j]==0):
        continue
    
    #B의 모든 원소가 2로 나누어떨어지도록
    while (b[j]!=0):
        for i in range(j,n):
            if ((b[i]%2)!=0):
                b[i]-=1
                ans+=1
                
        if (b[j]==0): # 주의
            break
        
        for i in range(j,n):
            b[i]//=2
        ans+=1
        
            
print(ans)