PS 풀이 및 정리/POI (2) 썸네일형 리스트형 POI Deque 문제(BOJ 8201번 Pilots , 10129번 작은 새) 먼저 Deque dp나 Deque를 이용한 테크닉에 잘 모르거나 익숙하지 않다면 다음 글을 보고 오자. https://chpark1111.tistory.com/8 자료구조 덱(deque)의 활용 덱은 앞뒤에서 빼고 넣을 수 있는 자료구조로, 처음 배울 때는 왜 배우지... 이거 과연 쓸데가 있을까?라고 생각했다. 하지만 이 자료구조를 이용하면 \(A_1,A_2,...,A_N\)이 주어질 때 임의의 상수 B에 대해 \(A_.. chpark1111.tistory.com 8201번 Pilots https://www.acmicpc.net/problem/8201 풀이 : 최솟값, 최댓값 덱을 만들고 덱에서 최댓값, 최솟값들의 인덱스 차이가 t 이상 나지 않도록 관리해주면서 가능한 구간의 최댓값을 갱신해주면 된다... POI Ice Skates (BOJ 8177번) 문제는 https://www.acmicpc.net/problem/8177 링크에서 풀어볼 수 있다. 문제 설명: 초기에 1~n 크기의 신발들이 각각 k쌍 씩 있다. 그리고 신발의 크기가 r인 사람은 r~r+d 크기의 신발을 신을 수 있다. 이때, m개의 상황이 생기는데, 각각의 상황은 2가지 종류 중 하나이다. (1) 신발 크기가 \(r_i\)인 사람 \(x_i\) 명이 온다. (2) 신발 크기가 \(r_i\)인 사람 \(x_i\)명이 나간다. (당연하지만 안 들어온 사람은 못 나간다.) 들어오는지 나가는지는 \(x_i\)의 부호로 구별할 수 있다. 각각의 상황이 발생했을 때, 현재 있는 모든 사람에게 위 조건을 만족하도록 신발을 분배할 수 있는지 여부를 묻는 문제이다. (들어오는 사람에게 신발을 주는 .. 이전 1 다음