[알고리즘] BOJ 12931 두 배 더하기

[BOJ] 12931 두 배 더하기 바로가기

📍 문제

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

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

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

---

📍 입력

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

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

---

📍 출력

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

---

📍 풀이

✍ 코드

# 12931  두 배 더하기 < 골드 4 >
from sys import stdin
N = int(stdin.readline())
B = list(map(int,stdin.readline().split()))
count = 0 # 연산 횟수
while sum(B): # 모든 B의 원소가 0이 될 때까지
  for i in range(N):
    if B[i] % 2 and B[i] > 0: # B[i]가 0보다 큰 홀수라면
      B[i]  -= 1 # 1 증가 연산
      count += 1 # 연산 횟수 + 1
  if sum(B): # 모든 B의 원소가 0이 아니라면
    # B의 모든 원소 2배 증가 연산
    for i in range(N):
      B[i]  = B[i] // 2
    count += 1 # 연산 횟수 + 1
print(count)