-
백준 18111번 마인크래프트PS 2020. 2. 11. 22:19
https://www.acmicpc.net/problem/18111
<접근방법>
직접 세보기 전까지는 답을 알 수 없는 완전탐색(?) 문제입니다.
저는 높이를 기준으로 위, 아래 블록의 수를 따로 빼서 작업을 진행하였는데
그냥 바로바로 계산하며 값 갱신해주는 것이 훨씬 깔끔하고 빠릅니다.
<코드>
#include <iostream> #include <algorithm> #include <vector> using namespace std; const int INF = 987654321; int n, m, b, h, h_up_cnt, min_h, max_h; int time = INF, res_h; int map[501][501]; vector<int> cal_need_cnt(int h) { int up_cnt = 0; int down_cnt = 0; vector<int> v; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (map[i][j] < h) { down_cnt += (h - map[i][j]); } else if (map[i][j] > h) { up_cnt += (map[i][j] - h); } } } v.push_back(down_cnt); v.push_back(up_cnt); return v; } int cal_time(int down_cnt, int up_cnt, int h) { int need_time = 0; need_time += (up_cnt * 2); need_time += down_cnt; return need_time; } void simul() { vector<int>v; for (int h = min_h; h <= max_h; h++) { v = cal_need_cnt(h); int down_cnt = v[0]; int up_cnt = v[1]; int ttime; if (down_cnt <= up_cnt + b) { ttime = cal_time(down_cnt, up_cnt, h); if (time > ttime) { time = ttime; res_h = h; } else if (time == ttime) { res_h = max(res_h, h); } } else { break; } } } int main() { cin >> n >> m >> b; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; min_h = min(min_h, map[i][j]); max_h = max(max_h, map[i][j]); } } simul(); if (time == INF) { cout << 0 << ' ' << min_h << '\n'; } else { cout << time << ' ' << res_h << '\n'; } return 0; }
<느낀 점>
'PS' 카테고리의 다른 글
백준 16958번 텔레포트 (2) 2020.02.14 백준 17136번 색종이 붙이기 (0) 2020.02.12 백준 16967번 배열 복원하기 (0) 2020.02.11 백준 17135번 캐슬 디펜스 (0) 2020.02.10 백준 16954번 움직이는 미로 탈출 (0) 2020.02.10