BOJ
BOJ::10836 여왕벌
BOJ Gold 5
BOJ::10836 여왕벌
- Link : BOJ::10836
- Level : Gold 5
시사점
- 좋은 시사점을 갖는 문제입니다.
- 처음 문제를 풀땐, 한 행과 한 열의 값만 바꿔주는 것은 알았지만, 복잡도가 MAXN(700) * 2 * 10^6이 되어 시간초과 가는 방법이었습니다.
- 해당 방법을 수정하여 대략.. 400 * 2 * 10^6 정도의 코드로 수정하였습니다.
- 아직까지도, 큰 차이를 느끼기 힘든 문제입니다.
- 하지만, 최적화 방법이 좋아서 기억해야할 문제입니다.
- 0, 1, 2 에 대해 모두 더하던 부분을 1, 2에 대해서만 연산을 수행해주면, 시간 복잡도는 1/3이나 줄어들게 됩니다.
키
- #가장 많이 자란 애벌레
이해(x)
- N * N격자에 초기에 1을 대입합니다.
- 이후 날짜가 가면서, 최좌측 열과 최상단 행에 있는 애벌레들의 성장값이 주어집니다.
- 모든 날짜가 경과한 후, 전체 애벌레들의 각 나이를 출력하는 문제입니다.
설계, 손 코딩(x)
- 손으로 중심이 되는 코드를 구현합니다.
- 값이 바뀌는 부분은 0열과 0행뿐입니다.
- 또한 값은 [n-1:0][0], [0][1:n-1] 순으로 주어집니다.
- 따라서, 0의 갯수, 1의 갯수, 2의 갯수를 입력받을때마다 필요한 위치의 값을 업데이트 해준다면,
- O(700 * 2) * 10^6이 되어 시간초과를 유발합니다.
- 따라서, 값을 입력받을때마다 애벌레의 나이를 바로 증가시키는 것이 아니라, line이라는 배열에 일단
업데이트 해줍니다.
- line은 one 부터 시작해서 two까지 진행하므로, 평균적으로 전체의 1/3의 시간 복잡도를 줄입니다.
- 따라서, 예상컨데 O(400) * 10^6의 복잡도 정도가 될 것 같습니다.
시간 복잡도
- O(400) * 10^6정도 예상됩니다.
공간 복잡도
손 코딩 후 문제 리뷰(x)
- 빼먹고 손 코딩 한 것이 있는지 확인합니다.
구현(x)
함수 List
업데이트 되는 변수
- 대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.
실제 구현
#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i, a, b) for(int i = a; i< b; i++)
const int MAXN = 1100 + 1;
const int MAXT = 1000 * 1000 + 1;
using namespace std;
int n, mxT;
int a[MAXN][MAXN];
int main(){
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> mxT;
vector<int> line(2 * n - 1, 1);
rep(i, 0, mxT){
int all012[3] = { 0 };
cin >> all012[0] >> all012[1] >> all012[2];
rep(i, all012[0], all012[0] + all012[1]){
line[i] += 1;
}
rep(i, all012[0] + all012[1], 2 * n - 1){
line[i] += 2;
}
}
rep(i, 0, n){
a[n - 1 - i][0] = line[i];
}
rep(i, n, 2 * n-1){
a[0][i - n+1] = line[i];
}
rep(i, 1, n){
rep(j, 1, n){
a[i][j] = max(a[i - 1][j - 1], max(a[i - 1][j], a[i][j - 1]));
}
}
rep(i, 0, n){
rep(j, 0, n){
if (j == n - 1){
cout << a[i][j];
}
else{
cout << a[i][j] << " ";
}
}cout << '\n';
}
return 0;
}
구현 후 코드리뷰 + 예제 돌려보기(x)
- 바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.