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

문제 설명

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

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

[문제]

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

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

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

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

 

[입력]

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

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

 

[출력]

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

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

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

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

 

[제한]

•  1≤T≤10000
•  1≤K<262144 = 2^18

[예제 입력 1]

2
5
17

[예제 출력 1]

5
1 1 1 1 1
5
1 2 2 4 3

---

풀이

 사실상 문제가 구현이나 알고리즘보다는 수학 문제에 가깝다.

 우선 제일 기본적인 증가하는 k개 짜리 수열이 있다고 가정을 해보면, 이 수열에서 얻을 수 있는 부분 수열은 kC1 + kC2 +....+ kCk 이다. 이 때 합을 생각해보면 2^k - 1인데, 이는 이항 계수의 성질에 대한 파스칼 삼각형을 생각해보면 된다.

파스칼 삼각형

 파스칼 삼각형에서 가로줄의 합은, 조합 공식 앞의 수 n에 대해 2^n을 만족한다. 물론 부분 수열의 길이가 0개 짜리인 건 없으니, 1을 빼면 2^n -1이 된다.

 일단은 이렇게 입력받은 수 K에 대해, K보다 2^n -1의 값이 작으면서 가장 근접한 n을 구하면, 가장 기본적인 증가하는 수열을 얻을 수 있다. 하지만 이후에 남은 수인 K - (2^n -1)을 위해 추가적으로 수열을 만들어야 한다. 하지만 K의 최대값이 2^18보다 작은 수이고, 수열의 가능한 최대 길이는 34이기 때문에 이런 수열을 반복으로 만들어서 단순 나열하기엔 문제가 생긴다.

 결국 남은 방법은 기존 수열 사이에 어떤 값을 추가로 넣어야 하는데, 만약 기존 수열에 포함된 값들 사이에서 수를 뽑아 사이에 넣게 되면 고려할 사항이 매우 복잡해진다. 하지만 이 때 기존 수열에 속한 값들보다 큰 값을 수열 사이에 넣으면 고려 사항이 단순해진다. 예를 들어 길이 8짜리의 수열이 존재한다.

1

2

3

4

5

6

7

8

 여기서 수열의 4번째에 값 뒤에 9를 삽입하면 모양이 이렇다.

1

2

3

4

9

5

6

7

8

 이 때 기존 수열의 부분 수열을 제외하고 추가로 만들어낼 수 있는 부분 수열의 개수를 고려하면, 9 한 개짜리 부분 수열 하나와, 9를 꼭 포함하며 앞의 숫자 1, 2, 3, 4 사이 에서 조합을 통해 만들 수 있는 부분 수열 개수인 4C1, 4C2, 4C3, 4C4 개가 존재한다. 9 뒤로는 9보다 작은 수들이기 때문에 증가하는 부분 수열을 만들 수 없으니, 4 번째 뒤에 값을 넣음으로써 추가로 만들 수 있는 부분 수열의 총 개수는 1 + 4C1 + 4C2 + 4C3 + 4C4 = 2^4가 된다.

 이를 단순히 수식화하면, 어떤 큰 값을 수열의 n번째 뒤에 넣게 되면, 이로 인해 추가되는 새로운 부분 수열의 개수는 2^n개이다. 이를 가지고 생각하면, 어떤 수든 2^n의 조합으로 만들 수 있으니 해결할 수 있다.

 결국 최종 알고리즘은 입력받은 K에 대해 우선 가장 기본적인 수열을 만들어내고, 이후 작은 남은 수를 2^t1, 2^t2...의 조합으로 표현한 다음 해당 값의 위치 뒤에 단순 더 큰 값을 삽입하면 된다.

 

예시) 

 예로 K = 400인 경우, 우선 조건에 맞는 가장 기본적인 수열의 길이 n = 8 을 구한다. (400> 2^8-1 = 255)

1

2

3

4

5

6

7

8

이후 남은 수는 145이며, 이를 2의 지수의 나열로 표현하면 145 = 2^7 + 2^4 + 2^0이 된다. 이를 순차적으로 큰 수부터 앞선 수열의 순차적으로 삽입하면, 

1

2

3

4

5

6

7

9

8

1

2

3

4

10

5

6

7

9

8

11

1

2

3

4

10

5

6

7

9

8

 

#include <iostream>
#include <vector>

using namespace std;

void solution(int K) {
	int firstLength = 0, length;
	int num = K, index = 1;
	vector<int> answer;

	//초기 수열 생성
	while (K >= ((1 << firstLength) - 1))
		++firstLength;

	--firstLength;

	for (index = 1; index <= firstLength; index++) {
		answer.push_back(index);
	}

	num = K - ((1 << firstLength) - 1);

	//남은 개수에 대해 처리
	while (num != 0) {
		length = 0;

		while (num >= (1 << length))
			++length;

		--length;

		answer.insert(answer.begin() + length, index++);

		num = num - (1 << length);
	}

	//필요 답 출력
	cout << answer.size() << '\n';

	for (int i = 0; i < answer.size(); i++)
		cout << answer[i] << ' ';
	cout << '\n';
}

int main() {
	//속도 차이가 어마어마하다.
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T, K;
	
	cin >> T;
	
	for (int i = 0; i < T; i++) {
		cin >> K;
		solution(K);
	}

	return 0;
}

---

결과