[BOJ]12970번: AB (c++)

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

12970번: AB

 

그리디

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, K;
	cin >> N >> K;
	
	// A 개수 : a, B 개수 : b
	for (int a = 1; a < N; ++a)
	{
		/*
			1. a + b = N
			2. a * b >= K
			일때, 문제에서 주어진 조건을 만족하는 문자열을 만들 수 있다.
		*/
		int b = N - a;
		if (a * b < K)
		{
			continue;
		}

		/*
			B를 b개만큼 먼저 배치한다음,
			각 A에 대해서 어디에 위치할 것인지 선택한다 
			(몇번째 B앞에 위치할 것인지)

			만약 A가 모든 B뒤에 위치한다면 (i,j)쌍 개수는 새로 증가하지 않는다.
		*/
		vector<int> pos_A(b + 1);
		for (int i = 0; i < a; ++i)
		{
			int after = min(b, K);
			
			++pos_A[b - after];
			K -= after;
		}

		/*
			각 B앞에 위치하기로 결정된 A개수만큼 모두 출력하고 나서
			각자리 B를 출력한다.
		*/
		for (int i = 0; i <= b; ++i)
		{
			for (int j = 0; j < pos_A[i]; ++j)
			{
				cout << 'A';
			}
			if (i < b)
			{
				cout << 'B';
			}
		}
		return 0;
	}

	// 문자열 구성이 불가능한 경우
	cout << -1;

	return 0;
}                          

 

 

정수 N과 K가 주어졌을 때, 다음 두 조건을 만족하는 문자열 S를 찾는 프로그램을 작성하시오.

- 문자열 S의 길이는 N이고, 'A', 'B'로 이루어져 있다.
- 문자열 S에는 0 ≤ i < j < N 이면서 s[i] == 'A' && s[j] == 'B'를 만족하는 (i, j) 쌍이 K개가 있다.

 

문자열은 A와 B로 이루어져 있으며,

각 A는 뒤에 있는 B의 개수만큼 (i, j)쌍을 이루게 되는데 이것이 총 K개가 되어야 한다.

 

이거 수학에서 앉을자리 고르기 문제잖아..?ㅋㅋㅋ

이 문제가 그리디 알고리즘인 이유는, 각각의 A가 최적의 앉을 자리를 골라야 하기 때문이다.

 

 

 

예를 들어 A 2개, B 3개의 자리를 배치한다고 하자.

B를 미리 늘어뜨려 놓으면

○B○B○B○ 처럼, 각각의 A는 4개의 자리 중에 하나를 선택할 수 있다.

저 자리를 C[0], C[1] ...이라 하면, C[2]는 B[2]앞에 위치한다는 뜻이다.

// A가 선택할수 있는 자리의 개수는 B 개수보다 1 많아진다
vector<int> pos_A(b + 1);

 

 

이 문제에서 자리 선택의 기준은 "뒤에 올 B가 몇개가 되면 좋겠는가" 이다. 

이루어야할 남은 쌍의 개수가 K개 이므로, 각 A는 뒤에 올 B의 개수가 K보다 크지 않도록 해야 한다. 

for (int i = 0; i < a; ++i)
{
	// 각 A는 뒤에 올 B의 개수가 K보다 크지 않도록 해야 한다. 
	int after = min(b, K);

	...
}

 

 

그리고 해당 하는 위치에 A카운트를 올려주어야 하는데, 인덱스값은 반대가 됨을 주의하자.

A자리 배정이 끝나면 K에서 새로 만들어진 쌍 개수를 빼준다.

for (int i = 0; i < a; ++i)
{
	int after = min(b, K);
	
	/*
		A의 위치는 뒤에 after개의 B가 있는 곳이다. 
		ex) b = 8, after = 3 일때, A는 pos_A[5]에 위치해야한다.
	*/
	++pos_A[b - after];
	K -= after;
}