문제 이해 단계
https://www.acmicpc.net/problem/20207
문제가 헷갈리게 적혀있어서 풀면서 문제를 이해하였다.
이런 문제는 좀 예시를 명확히 줬으면 좋겠다.
N개의 (시작일자, 종료일자)로 이루어진 블록이 들어오는데 이는 1 ~ 365 사이의 숫자로 이루어져 있다.
이를 열이 365까지 있는 2차원 맵에 1부터 채우는데 블록의 배열은 다음과 같은 규칙을 가진다.
1. 최대한 위쪽부터 채운다.
2. 각기 다른 블록의 시작과 끝이 연속(4,5,6) 이렇게 된다면 무조건 같은 라인(열)에 둔다.
3. 시작일이 같은 경우 긴 것부터 먼저 배열한다.
그리고 우리가 해야 하는 것은 코팅지의 길이를 정하는 것인데,
코팅지는 블록 전체를 감싸는 직사각형으로 만드는 것이다.
근데 이걸 또 최소화해야 해서 블록이 아예 떨어져 있다면 직사각형을 따로따로 만들어야 한다.
그건 그림을 보면 어느 정도 이해 갈 것이다.
어쨌든 이런 식으로 문제를 풀면 되는데, 이해하는데 한참 걸려서 짜증 났다.
문제 접근 단계
일단 코팅지를 구하는 과정을 생각해 보자.
위에 나타난 예시로 생각해 보면 생각보다 단순하다.
가로로 연결되어 있거나 세로로 겹쳐져있는 블록을 탐색하고,
W = (가장 긴 위치 - 가장 짧은 위치) // h = 블록의 층 WxH를 통해 직사각형의 넓이를 구해주면
오른쪽과 같이 구해줘야 할 답이 나오게 된다.
그러니까 결국 답을 구하기 위해서는
일단 블록들을 올바르게 배치해줘야 한다.
일단 이 문제에서 중요한 것은 층(행)이 생긴다는 것인데, 그 조건이 두 블록의 시간이 겹쳐야 한다는 것이다.
그런데 층의 개수나, 블록의 위치 같은 것은 정해져 있지 않고 유동적이다.
즉 순서를 잘 정해서 알아서 배치를 잘해야 한다.
이를 정확하게 하려면 시작시간이 빠른 순으로 정렬해야 한다.
왜냐하면 어떤 블록의 시작시간이 어떤 블록의 끝시간보다 크다면
그 블록 전체가 더 크다는 것을 의미하므로 하나만 검사해도 모든 블록을 알 수 있기 때문이다.
그리고 문제 규칙에서 시작일이 같은 경우 긴 것부터 먼저 정렬한다고 했으니,
(종료일 - 시작일)로 더 높은 것을 앞에 둔다.
나올 수 있는 케이스 분석
이제 정렬을 해서 배치하는 법을 알았다.
시뮬레이션을 돌리다 보면 다양한 경우가 나올 것인데, 이를 고려하면서 코드를 짜줘야 한다.
1. 다음 시작일이 (어떤 층 블록 종료 + 1) 일 때
해당 경우의 수는 문제 조건에서 무조건 이렇게 배치하라고 해줬기 때문에 최우선적으로 고려해줘야 한다.
그래서 다음 블록을 검사할 때 전체 층에 있는 블록의 현재 종료일에 대해 이를 확인해 준다.
존재하면 이 블록을 붙이고 해당 층의 종료일을 해당 블록의 종료일로 갱신해줘야 한다.
2. 다음 시작일이 (가장 긴 종료일+1) 보다 더 클 때
이게 무슨 말이냐면 다음 블록이 이전 블록들과 연결되어 있지 않을 때를 말하는 것이다.
위의 문제 예시를 보면 직사각형을 2개를 만들어서 계산하는데,
이는 종료일이 9일인 블록과 시작일이 11일인 블록이 떨어져 있기 때문이다.
여기서도 가장 긴 종료일을 계산해서 항상 다음 블록의 시작일과 비교하여
해당 값이 블록과 떨어져 있는지 계산해야 한다.
만약 떨어져 있다면 이제 새로운 직사각형이 필요하고 이전의 직사각형은 계산되어야 하기 때문에,
이때 현재까지의 height와 width를 가지고 넓이를 계산한다.
3. 다음 시작일이 어떤 층에 있는 블록의 종료일보다 작거나 같을 때
이럴 때는 간단하다.
그냥 새로운 층을 하나 만들어주고 해당 층의 종료일을 이 블록의 종료일로 설정해 준다.
이 3가지 케이스에 유의하면서 구현을 해주면 된다.
사실 구현 문제라서 아이디어는 간단하게 구현이 힘들었다.
문제 구현 단계
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 시작 일자, 종료 일자
struct Work{
int start;
int end;
};
// 시작 일자 빠른 순 - 길이가 더 긴 순
bool compare(Work a,Work b){
if(a.start == b.start)
return (a.end - a.start) > (b.end - b.start);
return a.start < b.start;
}
int main(){
int N;
scanf("%d",&N);
vector<Work> v(N);
for(int i = 0; i < N; i++) {
int S,E;
scanf("%d %d",&S,&E);
v[i] = {S,E};
}
sort(v.begin(),v.end(),compare);
int offset = v[0].start; // 길이 보정을 위한 오프셋
int width = v[0].end-offset+1; // 가로 길이
int height = 1; // 층 높이
int ans = 0;
vector<int> timeLine = {v[0].end};
bool firstCheck = false; // 마지막 블록 계산 확인 위해 넣음
for(int i = 1; i < v.size(); i++){
bool endFlag = false;
firstCheck = false;
// 다음 블록 시작일자 = 현재 층 종료일자 + 1
for(int j = 0; j < timeLine.size(); j++){
if(timeLine[j]+1 == v[i].start){
endFlag = true;
timeLine[j] = v[i].end; // 해당 층 갱신
width = max(width,v[i].end-offset+1); // 최대 길이 계산
break;
}
}
if(endFlag) continue;
// 다음 블록 시작 일자가 최대 길이보다 길 때(떨어져있을 때)
if(v[i].start - 1 > width+offset-1){
ans += (width * height); // 계산
// 초기화
height = 1;
offset = v[i].start;
width = v[i].end-offset + 1;
timeLine.clear();
timeLine.push_back(v[i].end);
// 해당 블록이 마지막 블록이라면 그 값으로 한번더 계산
if(i == v.size()-1) ans += (width* height);
firstCheck = true;
continue;
}
// 다음 블록의 시작일자 다른 한 층보다 길 때
for(int j = 0; j < timeLine.size(); j++){
if(v[i].start > timeLine[j]){
endFlag = true;
timeLine[j] = v[i].end;
width = max(width,v[i].end - offset + 1);
break;
}
}
if(endFlag) continue;
// 위 3가지에 해당x(모든 층보다 작은 경우)
timeLine.push_back(v[i].end); // 새로운 층 추가
// 그 층의 종료일자가 최대 길이보다 긴지 확인
width = max(width,v[i].end - offset + 1);
height++; // 높이 증가
}
// firstCheck로 끝난게 아니면 블록이 다 계산된게 아니므로 잔여값 계산
if(!firstCheck) ans += (width * height);
printf("%d",ans);
}해당 구현에서는 Work라는 구조체를 만들어
시작일자와 종료일자를 만들었다. 그리고 층을 나타내기 위해 벡터를 나타내어
그 벡터의 개수 자체가 층의 개수가 되고, 값은 그 층의 종료일이 된다.
여기서 좀 복잡한 건 width라는 길이를 정확히 계산해 주기 위해서 offset을 둔 것이다.
offset은 간단하게는 그냥 시작일자인데, 좌표로 나타나있기 때문에 이를 편하게 계산해 주기 위함이다.
그리고 firstCheck는 반복문이 끝났을 때 계산되지 않는 값이 남아있는지 확인하는 것이다.
코드에서는 다음 블록 시작일자가 최대 길이보다 길 때만 계산을 해주기 때문에 계산을 안 할 가능성이 높다.
그래서 이를 firstCheck로 체크하여 false라면 계산을 해준다.
계산하는 코드 안에 i == v.size() - 1은 마지막 블록이 (12,12) 등
넓이가 1일 때 계산이 되지 않는 것을 방지하기 위해서이다.
나머지 코드 설명은 위에 주석을 달아놨기 때문에 천천히 이해해 보길 바란다.
구현문제는 언제나 그렇듯 코드를 보고 넘기는 게 아니라
이해한 걸 토대로 자신의 코드를 짜보는 게 제일 도움 된다.
시행착오
이 문제는 진짜 진짜 힘들었다.
일단 문제 설명 자체가 애매하게 되어있어서 내가 맞게 이해한 건지도 모르겠었다.
안 헷갈리게 예시라도 제대로 줬으면 좋았을 텐데..
그냥 내가 이런 부분이 부족한 건가 싶다.
처음에는 이 문제를 BFS로 접근했다.
열도 365밖에 안되고 N도 1000밖에 안 돼서 가능할 줄 알았는데,
어떻게 접근해도 시간초과가 떠서 그 방식을 버리고 해당 방식으로 했다.
해당 방식으로 하니까 그래도 어느 정도 간단하게는 되는 것 같은데, 고려해줘야 할 점이 많았다.
내가 구현문제에 약한 점이 이런 부분인 것 같다.
고려해야 할 점을 제대로 모르는 것 같다.
예외점을 찾는 것이 제일 중요한데, 그 부분을 대충 넘어가다 보니 틀린걸 왜 틀렸는지 모른다.
그래도 문제 풀어서 좋긴 한데 이틀 걸려서 싫다.