[백준 129311번] 두 배 더하기(파이썬)

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

12931번: 두 배 더하기

이 문제는 유사한 문제가 하나있는데요

2022.07.07 - [알고리즘 공부] - [백준 12919번] A와 B_2 (파이썬)

[백준 12919번] A와 B_2 (파이썬)

바로 이 문제입니다.

문제를 푸는 원리는 완전 판박이입니다.

 

처음 문제를 읽을 때,

본능적으로 문제대로 따라갈려고 합니다.

처음에 0이 N개로 이뤄진 배열이 주어진다.

그럼 이걸 입력받은 B로 만들어야하는데...

어떻게 만들지?

만들 수 있나?

여기서 콜럼버스 달걀같은 발상 하나 할 수 있습니다.

'역연산해도 똑같지 않을까?'

 

1+1=2

2-1=1

 

같은 연산이지만 더하기가 빼기가 되었을 뿐입니다.

우리는 0으로 이뤄진 배열을

입력받은 B로 만드는 건 어렵지만

입력받은 B를 모두 0인 배열로 만드는 건

상대적으로 쉬운 편에 속합니다.

#백준 12931 두 배 더하기

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

time=0
#B를 역으로 계산
#더하는 건 뺴는걸로
#곱하는 건 나누는 걸로
while True:
    #만약 B의 모든 배열인자가 0이 되면 끝낸다
    if B.count(0)==N:
        break

    go=False
    #배열을 돌면서, 하나라도 홀수가 있다면 1을 빼준다
    for i in range(N):
        if B[i]%2==1:
            B[i]-=1
            time+=1
            go=True
            break
    if go==True:
        continue
    #만약 홀수가 없었다면, 모든 배열인자를 2로 나눠준다
    for i in range(N):
        B[i]/=2

    time+=1

print(time)

 

처음 문제를 구현할려하다가

'이거 구현이 빡센데'

라는 생각이 들 때

역으로 결과값을 기준으로

연산을 거꾸로 할 수 있다는 걸 배울 수 있는 문제입니다.