백준 31848- 엉성한 도토리 분류(C++)

문제 링크입니다. https://www.acmicpc.net/problem/31848

 

도토리를 구멍이 있는 분류기에 굴렸을 때, 몇번 째 구멍에서 빠지는지 구하는 문제입니다.

못빠지는 분류기를 지날 때마가 도토리의 크기는 1씩 작아집니다.

 

따라서 먼저 뒤에 있는 분류기에 위치 값을 더해주면서 어느 정도의 도토리까지 통과할 수 있는지를 구했습니다.

 

구멍의 크기를 갱신했으면, N번 째 도토리의 크기까지 몇번 째 구멍에서 먼저 빠지는지를 저장해줬습니다.

 

도토리의 크기를 입력 받았으면, 이전에 저장해두었던 값을 통해서 몇번 째 구멍에서 빠지는지 출력해줍니다.

(이분 탐색도 가능합니다.) 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;
int N, M;
pair<int, int> hole[100001];
int dotori[100001];
int Where[100001];
vector<int> ans;

void solve() {
	int fin = 0;
	for (int i = 1; i <= N; i++) {
		if (hole[i].first <= fin) continue;
		if (Where[N] != 0) break;
		for (int j = fin; j <= min(hole[i].first, N); j++) {
			if (Where[j] == 0) {
				Where[j] = hole[i].second;
			}
		}
		fin = hole[i].first;
	}
	for (int i = 1; i <= M; i++) cout << Where[dotori[i]] << " ";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &hole[i].first);
		hole[i].first += (i - 1);
		hole[i].second = i;
	}
	cin >> M;
	for (int i = 1; i <= M; i++) scanf("%d", &dotori[i]);
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.