백준 12931번: 두 배 더하기(Python/Java)

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

12931번: 두 배 더하기

 

 

 

접근

---

이런 형식의 문제는 여러 문제들을 통해서 몸소 확인했듯이, 0이 나열된 배열에서 목표 배열까지 만드는 것이 아니라, 목표 배열에서 역으로 연산해 0이 나열된 배열을 만드는 것이 훨씬 좋은 풀이 방법이다. 그렇다면 목표 배열을 기준으로 0으로 이루어진 배열을 만들어보자.

 

우선 주어진 연산을 반대로 생각해야 한다. 1을 더하는 것은 1을 빼는 것으로, 배열 전체를 2배로 만드는 것은 배열 전체의 값을 반으로 만드는 것이다. 여기까지 생각했다면 이미 문제의 반은 해결된 것이다.

 

내 풀이 방식은 이렇다. 배열 내 각 숫자를 각각 탐구한다. 지금 탐색한 숫자가 홀수인지, 짝수인지 확인한다. 홀수면 1을 빼주고 다시 확인한다. 짝수라면 2를 나누고 다시 확인한다. 이를 0이 될 때까지 반복한다. 앞서 얘기했듯이 1을 빼는 연산은 무조건 연산 횟수가 1씩 늘어난다. 하지만 나눈 횟수는 어떻게 처리할 것인가. 나눈 횟수는 가장 큰 숫자의 나눈 횟수를 생각하면 된다. 1을 빼든 2로 나누든 결국 가장 큰 수가 마지막까지 0이 되지 않고 남을 것이다. 예를 들어 길이가 3이고 [4, 2, 2]의 배열이 있다고 해보자. 2로 나눈다. [2, 1, 1]이 된다. 여기서 1번 인덱스와 2번 인덱스는 홀수니 각각 1씩 빼준다. [2, 0, 0]이 된다. 다시 2로 나눠준다. [1, 0, 0]이 된다. 이제 마지막 0번 인덱스의 값에 1을 빼주면 [0, 0, 0]이 된다.

 

무슨 얘기인지 감이 오는가? 결국 4가 0이 될 때까지 나누기를 두 번 했다. 이 2번의 나누기 안에 나머지 두 개의 2가 해야 하는 나누기가 포함되는 것이다. 즉, 배열의 각 숫자에서 가장 큰 숫자에 필요한 나누기의 횟수가 전체적으로 필요한 나누기의 횟수가 된다. 이제 이를 구현하기만 한다면 문제 해결이다.

 

 

 

풀이

---

Python

length = int(input())
board = list(map(int, (input()).split()))

divideNum = 0
minusNum = 0
for i in range(length):
    subNum = 0
    while True:
        if board[i] != 0:
            if board[i]%2 == 1:
                minusNum += 1
                board[i] -= 1
            else:
                board[i] //= 2
                subNum += 1

        if board[i] == 0:
            divideNum = max(divideNum, subNum)
            break

print((divideNum + minusNum))

 

Java

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        int length = Integer.parseInt(scan.nextLine());
        
        String[] firstLine = (scan.nextLine()).split(" ");
        int[] board = new int[length];
        for(int i = 0 ; i < length ; i++){
            board[i] = Integer.parseInt(firstLine[i]);
        }

        int divideNum = 0;
        int minusNum = 0;
        for(int i = 0 ; i < length ; i++){
            int subNum = 0;
            while(true){
                if(board[i] != 0){
                    if(board[i]%2 == 1){
                        minusNum++;
                        board[i]--;
                    }else{
                        board[i] /= 2;
                        subNum++;
                    }
                }

                if(board[i] == 0){
                    divideNum = Math.max(divideNum, subNum);
                    break;
                }
            }
        }

        System.out.println((divideNum + minusNum));

    }

}

 

 

 

후기

---

특별한 조건이 붙지 않는 이상 기존 문자열(혹은 배열)을 특정 문자열(혹은 배열)로 만드는 문제는 크게 어렵지 않게 풀 수 있었던 것 같다. 이 문제를 풀 때 오답을 많이 냈던 이유는 구현 방법이었다. 배열 내 각 숫자를 나눴을 때 홀수의 횟수가 1을 빼야 하는 숫자가 되는데, 이 부분을 생각해서 자꾸 어렵게 풀려고 했던 것이다. 가끔은 가장 간단한 방법이 정공법이 되기도 한다는 점을 기억해두자.