113. 증가하는 부분 수열의 개수 K(백준 22995) [JAVA, C++]

문제

문제 링크 : https://www.acmicpc.net/problem/22995

22995번: 증가하는 부분 수열의 개수 K

문제

자연수 $K$가 주어진다. 길이가 34 이하이면서 증가하는 부분 수열의 개수가 정확히 $K$개인 수열을 만드는 프로그램을 작성하자.

증가하는 부분 수열이 무엇인지 잘 모르는 친구들은 친절한 동원이가 준비한 아래 정의를 읽어보도록 하자.

• 부분 수열이란 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열하여 얻은 수열을 말한다.
• 증가하는 부분 수열이란 맨 처음 원소를 제외한 모든 원소가 바로 전 원소보다 큰 수열을 말한다. 다시 말해 길이가 $N$인 부분 수열 $A$가 있을 때 ( $A_{i-1} < A_i$ ,$2 \le i \le N$) 를 만족하면 $A$는 증가하는 부분 수열이다.

동원이는 위 정의에 따라 길이가 $1$인 부분 수열은 항상 증가하는 부분 수열임에 주의하면 좋겠다는 메모를 추신으로 남겼다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스마다, 만들어야 하는 수열의 증가하는 부분 수열의 개수를 나타내는 $K$가 주어진다.

출력

각 테스트 케이스에 대해 아래와 같이 두 줄로 구성된 답안을 출력한다.

첫째 줄에는 만든 수열의 길이 $N$을 출력한다. $N$은 $34$ 이하의 양의 정수여야 한다.

둘째 줄에는 만든 수열의 각 원소를 차례대로 공백으로 구분하여 출력한다. 수열의 각 원소는 $10^9$ 이하의 양의 정수여야 한다.

가능한 답안이 여러 가지 있으면 아무거나 출력해도 된다.

제한

• $1 \leq T \leq 10,000$ 
• $1 \leq M < 262,144 = 2^{18}$ 

 

풀이

우선, 수의 범위가 34자리이기 때문에,브루트 포스로는 절대 맞출 수 없다.

가장 간단하게 부분집합을 생각했을 때, N개으로 이루어진 배열로 만들 수 있는 부분집합의 수는 -> $2^N -1$개이다. (공집합 제외)

이 배열이 1...N순서라면 곧 증가하는 부분 수열을 $2^N -1$개 만들 수 있다는 것이다.

 

사실 여기까지 밖에 생각하지 못해 다른 사람의 풀이를 확인해봤다.

1 2 3 에서 2번째 자리에 5를 입력한 1 2 5 3 를 보자.

가능한 가짓수는 다음과 같을 것이다.

(1), (2), (3) + (5)

(1 2), (1 3), (2,3) + (1 5), (2 5)

(1 2 3) + (1 2 5) -> 7 + 4 = 11-> $2^3-1$ + $2^2$

한마디로, 중간의 n번째 자리에 삽입하게 되면 $2^n$개가 더 늘어나게 되는 것이다.

 

이를 이용해 풀이를 정리하면 다음과 같다.

1. 입력값을 넘지 않는 가장 큰 2진수 -1을 구하기 -> 이만큼 기본 배열 만들기
2. 나머지 값을 2진수로 표현해서 각각의 자릿수에 해당하는 자리에 이후 숫자 배치하기

역시 JAVA로는 시간 초과가 발생하여 C++로 했다

 

참고 : https://presentnine.tistory.com/51

22995번: 증가하는 부분 수열의 개수 K

 

코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;

import java.io.InputStreamReader;
import java.util.*;

class Main {

    static int N;
    static ArrayList<Integer> input = new ArrayList<>();
    /**
     * 2^n-1 찾기
     * 나머지 값을 2진수로 표현 -> 그 자리에 넣어주기
     **/
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++){
            input.add(Integer.parseInt(br.readLine()));
        }

        for(int i : input){
            addK(i);
        }
    }

    public static void addK(int in){
        if(in <= 34){
            System.out.println(in);
            for(int i=1; i<=in; i++){
                System.out.print(1 + " ");
            }
            System.out.println();
            return;
        }

        int idx = 0;
        int cur = in/2;
        ArrayList<Integer> answerList = new ArrayList<>();

        //가장 기본 배열 만들기
        while(cur > 0){
            cur = cur/2;
            answerList.add(idx + 1);
            idx++;
        }
        //남은 값 생각
        cur = in - (1 << (idx)) + 1;
        //2^m + 2^n + ...
        //1010111... -> 이진수 부분에서 시간을 단축할 수도 있을 것 같다.
        char[] binaryCur = Integer.toBinaryString(cur).toCharArray();
        for(int i=0; i< binaryCur.length; i++){
            if(binaryCur[i] == '1'){
                answerList.add(binaryCur.length -i-1, ++idx);
            }
        }
        //출력
        System.out.println(answerList.size());
        for(int i : answerList){
            System.out.print(i + " ");
        }
        System.out.println();
        return;
    }
}

코드 (C++)

#include <iostream>
#include <vector>
#include <utility>

using namespace std;


void addK(int a);
void printAnswer(int N, vector<int> answerList);

int main(int argc, char* argv[]) {

    //속도 빠르게
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, in;

    cin >> N;

    for(int i=0; i<N; i++){
        cin >> in;
        addK(in);
    }

    return 0;
}

void addK(int in){
    vector<int> answerList;

    if(in <= 34){
        answerList.assign(in, 1);
        printAnswer(in, answerList);
        return;
    }

    int idx = 0;
    int cur = in/2;

    while(cur > 0){
        cur = cur/2;
        answerList.push_back(idx+1);
        idx++;
    }

    cur = in - (1 << (idx)) + 1;

    for(int i=idx; i>=0; --i){
        if( (cur >> i) & 1 == 1){
            answerList.insert(answerList.begin() + i, ++idx);
        }
    }

    printAnswer(answerList.size(), answerList);
    return;
}

void printAnswer(int N, vector<int> answerList){
    cout << N << '\n';

    for(int i=0; i<answerList.size(); i++){
        cout << answerList[i] << ' ';
    }

    cout << '\n';
}

 

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!