문제
https://www.acmicpc.net/problem/18111
접근방법
최고점과 최저점을 저장한 후.
최고점에서 한 칸 제거하는 시간과 최저점에서 한 칸 추가하는 시간을 비교한다.
더 짧은 시간이 걸리는 쪽을 선택하고, 만약 최저점에서 추가할 블록이 없는 경우에는 무조건 최고점에서 한 칸 제거를 택한다.
코드
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#include <unordered_set>
#include <stack>
using namespace std;
#define FOR(i, n) for(int i=0;i<n;i++)
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX 987654321
#define MIN -987654321
int n, m, b;
int minute, height; //답이 여러개라면 가장 높은 걸 선택. -> 삭제와 삽입의 시간이 같은 경우 삽입.
int under = MAX, upper = MIN;
int main() {
FASTIO
cin >> n >> m >> b;
vector<vector<int>> ddang(n, vector<int>(m));
FOR(i, n) FOR(j, m) {
cin >> ddang[i][j];
upper = max(upper, ddang[i][j]);
under = min(under, ddang[i][j]);
}
while(upper != under) {
//upper는 한칸 내리는 시간과
//under 한칸 올리는 시간을 비교
//다만 under올릴 때는 블록이 그만큼 있는 지 세봐야함.
int timeA = 0, timeB = 0;
FOR(i, n) FOR(j, m) {
if (ddang[i][j] == upper) timeA += 2;
if (ddang[i][j] == under) timeB += 1;
}
//timeB가 가진 블록보다 작거나 같고, A보다 시간이 덜 걸리거나 같은 경우.
if (timeB <= b && timeB <= timeA) {
FOR(i, n) FOR(j, m) {
if (ddang[i][j] == under) ddang[i][j]++;
}
b -= timeB;
minute += timeB;
under++;
} else {
FOR(i, n) FOR(j, m) if (ddang[i][j] == upper) ddang[i][j]--;
minute += timeA;
upper--;
b += (timeA / 2);
}
}
cout << minute << " " << upper << endl;
return 0;
}
개선할 점
최고점에서 한 칸씩 제거할 때마다 가지고 있는 블록의 개수를 추가해줘야 하는데, 그 작업을 잊어서 한 번 틀렸다.
한번 테스트 케이스를 돌려보고 제출했으면 안 틀렸을 수 있는 문제였는데 아쉽다.
이래서 테스트케이스 만들어보는 것이 중요하다.
'코딩테스트 준비 > 백준' 카테고리의 다른 글
[백준 16918] - 봄버맨(구현) C++ (0) | 2024.03.20 |
---|---|
[백준 - 16926] -배열 돌리기(구현) C++ (0) | 2024.03.20 |
[백준 13460] - 구슬 탈출 2(BFS) C++ (1) | 2024.03.19 |
[백준 16234] - 인구 이동(bfs) C++ (0) | 2024.03.19 |
[백준 20437] - 문자열게임 2(슬라이딩 윈도우) C++ (0) | 2024.03.19 |