[백준] 2205번 : 저울 추 만들기[Java]

#풀이

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static int[] square = new int[20];
    static int findNum(int n){
        for(int i = 1; i<20; i++){
            if(n<square[i])return square[i];
        }
        return 0;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] ans = new int[n];

        square[0] = 1;
        for(int i = 1; i<20; i++){
            square[i] = square[i-1]*2;
        }
        for(int i = n-1; i>=0; i--){
            if(ans[i]!=0)continue;
            int num = findNum(i+1);
            ans[i] = num-(i+1);
            ans[num-(i+1)-1] = i+1;
        }

        for(int i = 0; i<n; i++){
            System.out.println(ans[i]);
        }

    }
}

#성능

#정리

1. 각 납덩어리에 대해, 해당 질량보다 크고 가장 가까운 2의 거듭제곱 수를 구한다.
2. 해당 거듭제곱 수를 기준으로, 납덩어리와 짝이 될 주석덩어리의 질량을 계산한다.
이때, 주석덩어리가 아직 사용되지 않았다면, 서로를 짝지어 ans 배열에 저장한다.
3. 자기 자신과 짝이 되는 경우도 허용된다. (예: (4,4)처럼)
4. 이렇게 하면 모든 납덩어리와 주석덩어리가 1:1로 매칭되며, 각 쌍의 합이 항상 2의 거듭제곱이 되는 저울추를 정확히 n개 만들 수 있다.

 

골드 문제인데 체감난이도는 많이 쉬웠다.