백준 18111 - 마인크래프트(C++)

문제 링크입니다. https://www.acmicpc.net/problem/18111

18111번: 마인크래프트

브루트포스 알고리즘 문제였습니다.

문제 조건

출력 예시

(0 ~ 256) 높이 사이에서 고르게 만들 수 있는지를 확인하는 문제였습니다.

블록을 쌓던가, 없애던가 총 2가지 방법이 있습니다.

따라서 먼저 해당 높이를 만들 수 있는지를 확인해야합니다.

B + 제거한 블록의 수 >= 쌓아야하는 블록의 수 -> 해당 조건이 맞을때만 시간 계산을 해야합니다.

 

해당 조건을 만족한다면 시간을 계산 해야합니다.

time = 제거한 블록의 수 * 2 + 쌓아야하는 블록의 수

이때 시간의 최솟값이 같다면 높이 중 큰것을 가져와야합니다.

 

문제 접근 방법

1. 높이마다 해당 블록이 몇개가 있는지를 저장한다.

2. 높이를 0 ~ 256 까지 확인한다.

3. 해당 높이에서 쌓을 수 있는지를 확인한다.

4. 쌓을 수 있다면 최소 시간과 최대 높이를 비교한다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>

using namespace std;
#define MAX 67000000;

int N, M, B;
int map[501][501];
int less_time = 1000000000;
int high = 0;
vector<pair<int,int>> number_block[257];

void can_make(int cnt) {
	int put_block = 0;
	int take_block = 0;
	int time = 0;
	for (int i = cnt+1; i <= 256; i++) {
		take_block += number_block[i].size() * (i - cnt);
	}
	for (int i = 0; i < cnt; i++) {
		put_block += number_block[i].size() * (cnt - i);
	}
	if (put_block > B + take_block) {
		return;
	}
	time += take_block * 2 + put_block;
	if (less_time >= time) {
		less_time = time;
		high = max(high, cnt);
	}
}

void solve() {
	for (int i = 0; i <= 256; i++) {
		can_make(i);
	}
	cout << less_time << " " << high;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> B;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> map[i][j];
			number_block[map[i][j]].push_back(make_pair(i, j));
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요