여왕벌
문제 해석
- 주어지는 애벌레가 커지는 정도의 정보를 이용하여 N번째날의 애벌레 상태를 구하는 문제입니다.
- 제일 왼쪽열과, 제일 위쪽 행의 에벌레들이 하루에 얼마나 크는지(0,1,2) 주어집니다.
- 나머지 에벌레들은 자신의 왼쪽,왼쪽위,위쪽 에벌레의 크기 중 가장 큰 값만큼 자신도 자랍니다.
- 왼쪽아래에서 시작하여 제일위쪽, 이후에 오른쪽으로 이동하며 읽었다고 가정합니다.
- 또한, 크기의 값은 감소하지않습니다.
설계(20)
- 처음에 지문을 이해하기가 아주 어려웠습니다.
- 입력에서 주어지는 정보는 각 날마다 0,1,2의 정보를 보여주는 것입니다.
- 예를들어 “1 2 2”이면 0이 1개, 1이 2개, 2가 2개로 “01122”식으로 생각하면 됩니다.
- 날짜 N번을 지나면서 2xM-1개의 애벌레의 크기를 갱신시켜주면 시간복잡도안에 들어서 통과할 줄 알았는데 시간초과가 났습니다.
- 그렇다면, 크기의 값은 감소하지 않는다는 키워드를 이용하여 1이 시작하는 지점과 2가 시작하는 지점을 각각 카운트합니다.
- 이후, arr[i] = arr[i-1]을 이용하여 부분합을 누적하는 방식을 이용합니다.
- 정해진 2xM-1개의 애벌레들을 맵에 저장하고, 다른 애벌레의 경우에는 왼쪽,왼쪽위,위 중 최대값을 갱신하도록합니다.
구현(40)
코드
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 700
int map[MAXN][MAXN];
int cache[2*MAXN];
int M,N;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> M >> N;
while (N--){
int a,b,c;
cin >> a >> b >> c;
cache[a]++;
cache[a+b]++;
}
for (int i = 1; i <2*M-1; i++){
cache[i] += cache[i-1];
}
int idx = 0;
for (int i = M-1; i>=0; i--){
map[i][0] = cache[idx++]+1;
}
for (int i = 1; i <M; i++){
map[0][i] = cache[idx++]+1;
}
for (int i =0; i<M; i++){
for (int j=0; j<M; j++){
if (!(i==0 || j ==0)){
map[i][j] = max(max(map[i-1][j], map[i-1][j-1]),map[i][j-1]);
}
cout << map[i][j] <<" ";
}
cout <<"\n";
}
return 0;
}
디버깅
- 부분누적합을 계산할 방법을 찾는데 시간이 오래걸렸습니다.
제출결과
- 284ms
마무리
- 부분누적합을 이용한 완전탐색문제였습니다. 감소하지 않는 점을 이용하여 펜윅트리와 같은 어려운 알고리즘을 이용하지 않고 부분누적합을 비교적 쉽게 구할 수 있었습니다.