- 선형탐색을 진행할 경우 O(N*M) 이므로 약 10,000,000,000 는 시간초과에 걸릴 것 같습니다.
- O(NlogN) 정렬 + O(M*logN) 이분탐색 으로 해결했습니다.
2. 주의사항
- 조건으로 인한 시간초과
3. 나의코드
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int Narr[100000];
int N, M;
bool existnum(int target) {
int ep = N - 1;
int sp = 0;
int mid;
while (sp<=ep) {
mid = (sp + ep) / 2;
if (Narr[mid] == target) { return true; }
else if (Narr[mid] < target) {
sp = mid + 1;
}
else if (Narr[mid] > target) {
ep = mid - 1;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> Narr[i];
}
sort(Narr, Narr+N); //이분탐색을 위한 정렬
cin >> M;
int target;
for (int i = 0; i < M; i++) {
cin >> target;
cout << existnum(target)<<"\n";
}
return 0;
}
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int N, M;
vector<long long> arr;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> M;
long long tt;
for (int i = 0; i < N; i++) {
cin >> tt;
arr.push_back(tt);
}
int tmpsum = arr[0];
int resultcount = 0;
int sp = 0;
int ep = 0;
while (1) {
if (tmpsum == M) {
resultcount++;
tmpsum -= arr[sp];
sp++;
ep++;
if (ep == N) break;
tmpsum += arr[ep];
}
else if (tmpsum < M) {
ep++;
if (ep == N) break;
tmpsum += arr[ep];
}
else if (tmpsum > M) {
tmpsum -= arr[sp];
sp++;
}
}
cout << resultcount;
return 0;
}
- 문제는 간단하고 이해도 어렵지 않지만, 시간제한이 0.3초 인 점을 감안하여야 합니다.
- 문제에서의 단계대로 차례차례 진행해줍니다.
2. 주의사항
- 전 처음에 시간제한 및 어린나이부터 진행되어야 한다는 문제를 보고 우선순위 큐를 생각해서 접근하였는데,
- 정답은 잘 뽑아내는 것 같으나, 시간초과가 계속 되어 결국 자료형을 vector로 바꿔서 봄에만 정렬을 하여 사용하였습니다.
- vector를 사용하자니, 죽은 나무를 뽑아내는 것이 문제였는데, vector는 index로 쉽게 접근이 가능하나 원하는 위치의데이터를 맘대로 뽑기는 어렵습니다.
- 그래서 양분이 부족해지는 지점이 딱 왔을 때, 그 이차원벡터배열의 맨뒤부터 양분/2를 더해주면서 pop_back() 해주었습니다.
3. 나의코드
#include<bits/stdc++.h>
using namespace std;
int n, m, K;
int ground[11][11]; // 양분의 양
vector<int> treeageset[11][11]; //나이 기준 정렬
int s2d2[11][11];
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
int tmpv[1001];
int presize[11][11];
void inputs() {
cin >> n >> m >> K;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
ground[i][j] = 5;
cin >> s2d2[i][j];
}
}
int x, y, z;
for (int i = 0; i < m; i++) {
cin >> x >> y >> z;
treeageset[x][y].push_back(z);
}
}
bool boundcheck(int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= n);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inputs();
for (int i = 0; i < K; i++) { //1년
//봄
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
if (treeageset[j][k].empty()) continue;
int tmpground = ground[j][k];
ground[j][k] = 0;
sort(treeageset[j][k].begin(), treeageset[j][k].end());
int vsize = treeageset[j][k].size();
for (int a = 0; a < vsize; a++) {
if (tmpground >= treeageset[j][k][a]) {
tmpground -= treeageset[j][k][a];
treeageset[j][k][a]++;
}
else {
for (int b = vsize - 1; b >= a; b--) {
ground[j][k] += treeageset[j][k][b] / 2;
treeageset[j][k].pop_back();
}
break;
}
}
ground[j][k] += tmpground; //남은 양분+죽은나무의 양분
}
}
//새로 추가되는 나무들은 번식시키지 않기 위해서
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
presize[j][k] = treeageset[j][k].size();
}
}
//가을 번식
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
for (int a = 0; a < presize[j][k]; a++) {
if (treeageset[j][k][a] % 5 == 0) {
for (int b = 0; b < 8; b++) {
int nextx = j + dx[b];
int nexty = k + dy[b];
if (boundcheck(nextx, nexty)) {
treeageset[nextx][nexty].push_back(1);
}
}
}
}
ground[j][k] += s2d2[j][k]; //양분 보급
}
}
}
int resultsum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
resultsum += treeageset[i][j].size();
}
}
cout << resultsum;
return 0;
}
