[Python] 백준 12931 두 배 더하기

🧑‍💻 [Python] 백준 12931 두 배 더하기

Gold 5 - 그리디

 

제일 중요하게 생각해야 하는 것은 B에서 배열 A를 만드는 것이다

즉 B에 있는 원소들을 다 0으로 만들어야 하는 것

• 즉 B에서 값 하나씩 1을 빼는 것
• 그리고 B에서 모든 값을 2로 나눠서 0을 만드는 것으로 반대로 생각하면 된다

---

 

문제풀이

• 최소를 구하는 것이니깐 모든 값을 2로 나누는 것을 먼저 생각한다
  • for문을 통해, 모든 숫자가 숫자 % 2 == 0 로 떨어지면, count에 1을 더한다
  • 그리고 for문을 순회할 때에, 각 숫자들을 2로 나눈 것을 temp 리스트에 넣는다
  • 그리고 만약에 for문을 아무 문제 없이 순회를 했다면, temp리스트를 B로 업데이트 한다
• 반대로 위에서 for문을 통해 순회를 했는데, 홀수를 구한다면?
  • 그 for문은 바로 멈춘다
  • command를 "add"로 바꿔준다
  • 그리고 다시 처음부터 for문을 돌면서 B에서 홀수 값들을 1로 빼준다
  • 빼줄때마다 count에 1을 더해준

---

 

코드

N = int(input())
B = list(map(int, input().split()))
count = 0

temp = [0] * N


while sum(B) != 0:
    command = "multiply"

    # 모든 숫자가 짝수인지 홀수인지 확인하는 for문
    for i in range(N):
        if B[i] % 2 != 0:
            command = "add"
            break
        else:
            temp[i] = B[i] // 2

    if command == "multiply":
        B = temp
        temp = [0] * N
        count += 1

    # 홀수가 발견 될 때에, 실행하는 for문
    else:
        for i in range(N):
            if B[i] % 2 != 0:
                B[i] -= 1
                count += 1

print(count)