문제
팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.
목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.
lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.
좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.
1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.
단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.
입력
첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)
둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.
https://www.acmicpc.net/problem/18111
풀이
일단 2차원구조가 굳이 필요없기에 모든 블럭의 높이를 N*M크기의 일차원배열에 할당했다.
처음에는 현재블럭의 최대높이, 최소높이를 가지고 블럭을 깎는 함수, 쌓는함수따로 구분해서 어떤 로직에따라 나눠 실행했으나..
너무많은 분기가 생겨 포기하고 근본적인 생각을 떠올려보기로했다.
N,M의 최대가 각각 500이면 N * M = 250000
블럭의 최대높이가 0~257이니 곱하면 64250000. 최대 6천만의 연산 쓰인다.
대충 1초면 1억회정도의 연산을 수용할수 있으니..
그러면 0층부터 256층까지 블럭의높이를 강제로 만들어보면 어떨까? 해서 코드를 작성해보았다.
그럴려면 블럭의높이를 정렬해야하고, 인벤토리에 블럭이있어야 블럭을 쌓을 수 있으므로, 블럭을 깎는것이 선행되어야하니; 내림차순정렬해서 블럭을 먼저 깎아 확보하고 그다음 블럭을 쌓는방식을 써보았다.
- 블럭을 깎는 부분
cur가 블럭의 높이를 나타내는 map을 순회할 인덱스를 나타낸다.
- 블럭을 쌓는 부분
중요한점은 블럭을 쌓을려고 하는데 인벤토리의 블럭이 부족해지면 해당 k층을 만들수 없는것이고, 결론적으로 맵에있는 블럭의 갯수는 고정적이니, k+1층또한 고르게 만들 수 없는것. 따라서 이경우 현재까지 구한 최적의 시간과 층을 출력하고 프로그램을 종료시켜야한다.
또 최소 시간일때 높이H를 갱신하는데, 문제에서 같은 최소시간이면 높이가 높은것을 출력하라 했으므로,
min_T >= t 서로 같음을 조건에 넣어주어야한다.
실버2문제치고는 한가지 아이디어를 떠올리기 어려웠다.
시간복잡도를 통해서 굳이 표현하면 브루트포스방법으로 구하는 아이디어를 생각해냈다면 실버와 적합한데,
이보다 더 효율적인 코드를 생각하다가는 더 어려운방법으로 문제를 접근하게된다..
PS문제를 단순하게 생각해볼 필요가 있다..
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define MAX 500*500 + 1
using std::vector; using std::stack; using std::queue; using std::deque; using std::tuple;
using std::string; using std::pair; using std::make_tuple; using std::tie;
using std::sort; using std::swap;
using std::make_pair; using std::max_element; using std::min_element; using std::bitset; using std::to_string;
using std::fill; using std::priority_queue; using std::greater;
//using std::max; using std::min; using std::map;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef pair<int, double> pid;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, char> pic;
typedef pair<char, int> pci;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef pair<string, string> pss;
ll N, M, B, size, H, min_T=LLONG_MAX;
int map[MAX];
void init();
void func();
void init() {
scanf("%lld%lld%lld", &N, &M, &B);
size = N * M;
for (int i = 0; i < size; i++)
scanf("%d", &map[i]);
sort(map, map + size, greater<>()); //내림차순 정렬
}
void func() {
int res = 0;
for (int k = 0; k <= 256; k++) { //모든 블럭의높이를 k층으로 만들어본다.
ll b = B; //사용가능한 블럭수
ll t = 0; //사용될 총 시간
bool possible = true;
//1.블럭을 깎는다 - 각2초
int cur = 0;
while (map[cur] >= k && cur < size) { //k층보다 같거나 클때까지만
int gap = map[cur] - k; //깎아야할 갯수
t += gap * 2; //한칸깎는데 2초 소요
b += gap; //깎은블럭 인벤토리에 저장
cur++;
}
//2.블럭을 쌓는다 - 각1초
while (cur < size) { //나머지 블럭 모두 순회
int gap = k - map[cur]; //쌓아야할 갯수
b -= gap; //인벤토리의 블럭 사용
if (b < 0) { //인벤토리의 블럭이 부족하면 탐색종료
printf("%lld %lld", min_T, H);
return;
}
t += gap; //한칸쌓는데 1초 소요
cur++;
}
//지금껏 최소시간또는 동일한시간이면 높이를 저장
if (min_T >= t) {
H = k;
min_T = t;
}
}
printf("%lld %lld", min_T, H);
}
int main(void) {
init();
func();
return 0;
}