[3일차] 자료구조 O - 3020: 개똥벌레

골드 Ⅴ

 

#include <iostream>
using namespace std;

int N, H;
int noo[500000] = { 0, };//인덱스 H-1 까지 채워질거임

int main() {
	scanf("%d%d", &N, &H);
	int size;
	for (int i = 0; i < N; i++) {
		scanf("%d", &size);

		if (i % 2 == 0) {//종유석 -> noo[0]에서 시작, noo[size - 1]까지 채움
			noo[0]++;
			noo[size]--;
		}
		else {//석순 -> noo[H-1]에서 시작, noo[H - size]까지 채움
			noo[H - size]++;
		}
	}

	int desMin = N + 1;
	for (int i = 1; i < H; i++) {
		noo[i] += noo[i - 1];
		if (desMin > noo[i]) desMin = noo[i];
	}
	int minCnt = 0;
	for (int i = 0; i < H; i++) {
		if (noo[i] == desMin) minCnt++;
	}
	printf("%d %d", desMin, minCnt);
}

 

누적합 문제

 

근데 보통 누적합 문제들이 캐시 쓰는 데에 비해서

캐시는 쓰는게 아니라.. 음 머라해야될까

동굴이라는 배열 noo[500000]에 하나씩 N개(20만개정도였던듯)씩이나 되는 종유석과 석순을 채워넣는게

너무 오래걸리니까? -> N개의 정보가 거의 다 H높이로 들어왔다고 하면.. 배열 전체를 다 훑는 작업을 N번 해줘야 함..

(배열 슥 슥슥 하고 N번 훑기)

일단 종유석과 석순이 어디어디에 있다 라는건 가볍게 표시해주고

(- > 이거만 보면... LIS인가 했을 때 스위핑 같기도 한데 약간 비슷한 느낌)

배열은 마지막에 한 번만 훑는거로... (배열 한 번만 훑기)

 

물론 뒤에 desMin이랑 또 cnt도 구해야 돼서 두번 더 훑긴 하는데

N(20만번쯤) 훑는거랑 세번이랑은 차이가 많이 있지

 

카테고리에 이분탐색이 있는데.. 왜있는지는? 글쎄

 

굳!