ALOHA 월반 1주차 - 완전탐색 / 그리디 / 분할정복

1. [2217] 로프 (Silver IV)

의도한 태그: Greedy (Easy)

만약 로프를 \( c \)개 쓸 거라면, 자명하게 가장 강한 \( c \)개의 로프를 써야 합니다.

그리고, 그 때 들 수 있는 중량은 \( c \times \min(A_{1}, A_{2}, \ldots, A_{c}) \)가 됩니다.

만약 로프의 강도가 (큰 게 먼저 오도록) 정렬되어있다면, 답은 \( c \times A_{c} \)가 됩니다.

 

그러니, \( c \)를 \( 1 \)부터 \( N \)까지 다 돌려주면서 답을 찾으면 됩니다.

2. [2630] 색종이 만들기 (Silver II)

의도한 태그: Divide and Conquer (Easy)

현재 크기의 색종이를 보면서, 한 가지 색깔로만 칠해졌다면 그대로 붙여주고,

그렇지 않으면, 4가지 구간으로 색종이를 나눠서 재귀적으로 탐색해주면 됩니다.

int arr[130][130];

int cnt0 = 0, cnt1 = 0;
void rec(int sty, int stx, int siz){ int edy = sty+siz, edx = stx+siz;
	bool chk0 = 1, chk1 = 1;
	for (int y = sty; y < edy; y++){
		for (int x = stx; x < edx; x++){
			chk0 &= (arr[y][x] == 0); chk1 &= (arr[y][x] == 1);
		}
	}
	if (chk0){ cnt0 += 1; return; } if (chk1){ cnt1 += 1; return; }
	int mdy = sty+edy >> 1, mdx = stx+edx >> 1;
	rec(sty, stx, siz>>1); rec(sty, mdx, siz>>1);
	rec(mdy, stx, siz>>1); rec(mdy, mdx, siz>>1);
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cin >> arr[i][j]; }
	}
	rec(1, 1, n);
	cout << cnt0 << endl << cnt1;
}

3. [24268] 2022는 무엇이 특별할까? (Silver II)

의도한 태그: Brute Force (Normal)

\( d \)진법 수 중에서 모든 수가 다른 수들은 \( O(d!) \)개 있습니다.

순열을 생각해보면 당연하죠.

 

그러니 그 수들을 하나하나 돌려보면서 답이 될 수 있는지 판별해주면 됩니다.

\( d \)진법 수가 \( 0 \)으로 시작하는 경우는 고려하면 안 됨에 주의하세요!

vector<ll> res;

void Main(){
	ll n, d; cin >> n >> d;
	vector<int> v;
	for (int i = 0; i < d; i++){ v.push_back(i); }
	do{
		if (v[0] == 0){ continue; }
		ll val = 0;
		for (int i = 0; i < d; i++){ val *= d; val += v[i]; }
		res.push_back(val);
	} while( next_permutation(all(v)) );
	//for (ll x : res){ cout << x << ' '; }
	auto it = upper_bound( all(res), n );
	if (it == res.end()){ cout << -1; }
	else{ cout << *it; }
}

4. [16198] 에너지 모으기 (Silver I)

의도한 태그: Brute Force (Normal)

구슬을 빼내는 경우의 수가 \( 8! \)밖에 되지 않습니다.

그러니, 백트래킹을 돌려주면서 이 모든 경우를 다 돌려주면 됩니다.

int n; int arr[12];

bool chk[12]; int ans = 0;
void btk(int cnt, int res){
	if (cnt == 2){ ans = max(ans, res); return; }
	for (int i = 2; i < n; i++){
		if (!chk[i]){ continue; }
		chk[i] = 0;
		int st = i, ed = i;
		while (!chk[st]){ st -= 1; } while (!chk[ed]){ ed += 1; }
		btk(cnt-1, res + arr[st]*arr[ed]);
		chk[i] = 1;
	}
}

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; chk[i] = 1; }
	btk(n, 0); cout << ans;
}

5. [14225] 부분수열의 합 (Silver I)

의도한 태그: Brute Force (Easy)

부분 수열을 고르는 경우의 수는 총 \( 2^N \)가지가 있습니다.

그러니, 이를 모두 돌려주면서 문제의 답을 계산해주면 됩니다.

int n; int arr[22];

const int N = 1048576; bool chk[1048580];
void btk(int idx, int val){
	if (val >= N){ return; }
	if (idx > n){ chk[val] = 1; return; }
	btk(idx+1, val); btk(idx+1, val+arr[idx]);
}

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	btk(1, 0);
	for (int ans = 1; ; ans++){
		if (!chk[ans]){ cout << ans; return; }
	}
}

6. [19539] 사과나무 (Silver I)

의도한 태그: Greedy (Hard)

하루에 뿌리는 물의 양은 \( 3 \)이기 때문에, \( X \)일 물을 뿌린 뒤에는 나무의 총 크기가 \( 3X \)가 되어야 합니다.

그러니, 나무의 총 크기가 \( 3 \)의 배수가 아니라면 NO가 답이고, 그렇지 않다면 물을 뿌린 일 수 \( X \)를 알 수 있게 됩니다.

 

그럼 물은 어떻게 뿌려야 할까요?

잠시 1과 2를 같이 뿌려야 한다는 걸 잊고, 그냥 2를 최대한 많이 뿌려봅시다.

이는 각 나무별로 \( \lfloor A_{i}/2 \rfloor \)의 합을 계산해주는 방식으로 구할 수 있습니다.

 

그 뒤로, 2를 \( X \)회 이상 뿌릴 수 있다면 YES, 아니면 NO를 출력하면 됩니다.

 

이렇게 해도 답을 구할 수 있는 이유는,

우선 1과 2를 뿌리는 '순서'는 '최종' 결과에 영향을 미치지 않으며 (1과 2를 '동시에' 뿌린다는 걸 잊어도 되는 이유)

2를 덜 뿌린다고 해도 이를 2개의 1로 대체할 수 있기 때문입니다. (2를 뿌릴 수 있는 최대 횟수만 찾아도 되는 이유)

ll arr[100020];

void Main(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	ll two=0, sum = 0;
	for (int i = 1; i <= n; i++){
		two += arr[i] / 2;
		sum += arr[i];
	}
	if (sum%3 != 0 || two < sum/3){ cout << "NO"; }
	else{ cout << "YES"; }
}

7. [1461] 도서관 (Gold V)

의도한 태그: Greedy (Normal)

우선, 한 번의 이동에 양수랑 음수를 동시에 지나는 경우는 고려하지 않아도 됩니다.

중간에 0을 지나면서 다시 책을 리필하는 게 더 좋기 때문이죠.

그러니 앞으로는 한 쪽 방향에 대해서만 풀이하겠습니다.

 

당연하겠지만, 멀리 있는 점들을 한 번에 처리하는 게 1번만 멀리 갔다 오게 되기 때문에

더 좋은 해를 주게 될 것입니다.

그러니, 가장 멀리 있는 점들부터 M개를 들고 갔다 오면 됩니다.

갔다 와야 하기 때문에, 길이의 2배를 답에 더해줘야 함에 주의하세요.

 

모든 처리가 끝난 뒤, 이동 거리가 가장 길었던 이동에 대해 그만큼의 길이를 빼주면 됩니다.

마지막 이동 뒤에는 다시 돌아올 필요가 없기 때문이죠.

int arr[120];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	sort(arr+1, arr+n+1);
	int ans = 0, cnt = 0, mx = 0;
	for (int i = 1; i <= n; i++){
		if (arr[i] > 0){ break; }
		if (cnt == 0){ cnt = m; ans += abs(arr[i]); mx = max( mx, abs(arr[i]) ); }
		cnt -= 1;
	}
	cnt = 0;
	for (int i = n; i >= 1; i--){
		if (arr[i] < 0){ break; }
		if (cnt == 0){ cnt = m; ans += abs(arr[i]); mx = max( mx, abs(arr[i]) ); }
		cnt -= 1;
	}
	cout << 2*ans-mx;
}

8. [14601] 샤워실 바닥 깔기 (Large) (Gold I)

의도한 태그: Divide and Conquer (Hard)

2가지 재귀를 짜면 됩니다.

dnc1: \( 2^N \times 2^N \) 크기에서 한 칸이 빠진 판에 L 트로미노를 채우는 함수

dnc2: \( 2^N \times 2^N \) 크기의 L 트로미노를 빠짐없이 채우는 함수

 

그럼, 아래와 같은 방식으로 재귀적으로 채워주면 됩니다.

dnc1은, 크기가 더 작은 dnc1과 방향이 정해진 dnc2를 부른다.

dnc2는, 크기가 작은 4개의 dnc2를 부른다. 비어있는 칸의 방향에 주의하자.

int y, x;
int f(int y1, int x1, int siz){ int y3 = y1+siz, x3 = x1+siz;
	int y2 = y1+y3 >> 1, x2 = x1+x3 >> 1;
	//cout << "F " << y1 << ' ' << y3 << "   " << x1 << ' ' << x3 << "   " << y << ' ' << x << endl;
	if (y < y2 && x < x2){ return 0; }
	if (y < y2 && x >= x2){ return 1; }
	if (y >= y2 && x >= x2){ return 2; }
	if (y >= y2 && x < x2){ return 3; }
}

const int dy[4] = {0, 0, 1, 1}, dx[4] = {0, 1, 1, 0};
const int dy2[4] = {-1, -1, 1, 1}, dx2[4] = {-1, 1, 1, -1};

int arr[130][130];
int cnt = 0;
void dnc2(int y1, int x1, int siz, int emp){ int y5 = y1+siz, x5 = x1+siz;
	//cout << "F2 " << y1 << ' ' << y5 << "   " << x1 << ' ' << x5 << "   " << emp << endl;
	if (siz == 2){ cnt += 1;
		if (emp != 0){ arr[y1][x1] = cnt; }
		if (emp != 1){ arr[y1][x1+1] = cnt; }
		if (emp != 2){ arr[y1+1][x1+1] = cnt; }
		if (emp != 3){ arr[y1+1][x1] = cnt; }
		return;
	}
	int y3 = y1+y5 >> 1, x3 = x1+x5 >> 1;
	int y2 = y1+y3 >> 1, x2 = x1+x3 >> 1;
	int y4 = y3+y5 >> 1, x4 = x3+x5 >> 1;
	dnc2(y2, x2, siz/2, emp);
	int d2 = (emp+2)%4;
	int d3 = (d2+1)%4, d1 = (d2+3)%4;
	dnc2(y2 + siz/4*dy2[d2], x2 + siz/4*dx2[d2], siz/2, emp);
	dnc2(y2 + siz/4*dy2[d3], x2 + siz/4*dx2[d3], siz/2, d1);
	dnc2(y2 + siz/4*dy2[d1], x2 + siz/4*dx2[d1], siz/2, d3);
}
void dnc1(int y1, int x1, int siz){ int y2 = y1+siz, x2 = x1+siz;
	//cout << "F1 " << y1 << ' ' << y2 << "   " << x1 << ' ' << x2 << endl;
	int emp = f(y1, x1, siz);
	//cout << "EMP " << emp << endl;
	int yp = y1 + siz/2*dy[emp], xp = x1 + siz/2*dx[emp];
	if (siz > 2){ dnc1(yp, xp, siz/2); }
	dnc2(y1, x1, siz, emp);
}

void Main(){
	int n; cin >> n >> x >> y; int m = 1<<n;
	arr[y][x] = -1;
	dnc1(1, 1, m);
	for (int y = m; y >= 1; y--){
		for (int x = 1; x <= m; x++){ cout << arr[y][x] << ' '; }
		cout << endl;
	}
}

9. [20929] 중간 (Gold I)

의도한 태그: Divide and Conquer (Hard)

길이가 각각 \( 2N \)인 두 배열 \( A, B \)가 주어졌다고 해봅시다.

뭔가 이진 탐색을 돌리면 될 것 같은 제한이니, \( A_{N}, B_{N} \)을 물어봅시다.

 

편의상 \( A_{N} < B_{N} \)이라고 가정해봅시다. (그렇지 않다면, 두 배열을 바꿔서 생각해보면 됩니다.)

이 경우, \( A_{N} \)은 \( A_{N+1}, A_{N+2}, \ldots, A_{2N} \)과 \( B_{N}, B_{N+1}, \ldots, B_{2N} \)보다 작다는 결론이 나옵니다.

즉, \( A_{N} \)은 \( 2N+1 \)개의 수보다 더 작은 수가 되므로, 답의 후보가 될 수 없습니다.

또한, \( A_{N} \)보다 더 작은 \( A_{1}, A_{2}, \ldots, A_{N-1} \)도 답의 후보에서 제외됩니다.

 

하지만 이는 배열 \( A \)의 후보만 줄이는 것이 아닙니다.

\( B_{N+1} \)은 \( B_{1}, B_{2}, \ldots, B_{N} \)과 \( A_{1}, A_{2}, \ldots, A_{N} \)보다 크다는 결론이 나옵니다.

즉, \( B_{N+1} \)은 \( 2N \)개의 수보다 더 큰 수가 되므로, 답의 후보가 될 수 없습니다.

또한, \( B_{N+1} \)보다 더 큰 \( B_{N+2}, B_{N+3}, \ldots, B_{2N} \)도 답의 후보에서 제외됩니다.

 

2번의 쿼리로 두 배열의 길이가 절반이 되니, 약 \( 2k \)번의 쿼리로 문제를 해결할 수 있습니다.

int ask(char arr, int idx){
	cout << "? " << arr << ' ' << idx << endl << flush;
	int x; cin >> x; return x;
}
void ans(int x){ cout << "! " << x << endl << flush; }

void Main(){
	int N; cin >> N; int n = 0; while (1<<n != N){ n += 1; }
	int ai = 0, bi = 0;
	for (; n; n--){
		int N = 1<<n;
		int a = ask('A', ai + N/2), b = ask('B', bi + N/2);
		if (a < b){ ai += N/2; } else{ bi += N/2; }
	}
	int a = ask('A', ai+1), b = ask('B', bi+1);
	ans(min(a, b));
}