본문 바로가기

DP

POI 18회 스테이지3 문제2. Monotonicity 2 문제 설명 https://www.acmicpc.net/problem/8195 풀이 * 아래 풀이는 POI 공식 사이트에서 볼 수 있는 풀이(폴란드어로 쓰여 있음)를 참조했습니다. (https://oi.edu.pl/) 1. 개요 우리가 해결할 문제는, 주어진 수열 \(a_1, a_2, \dots, a_n\)의 부분수열 \(a_{b_1}, a_{b_2}, \dots, a_{b_k}\) 중, 모든 \(1 \le i \le n-1\)에 대해 \(i\)번째 항과 \(i+1\)번째 항 사이에 \(a_{b_i} \,\langle s_i \rangle\, a_{b_{i+1}}\)이 성립하는 것 중 가장 긴 것을 찾는 것이다. 여기서 \(\langle s_i \rangle \)는 부등호 또는 등호인 \(s_i\)를 \(.. 더보기
SCPC 2017 2차예선 5번 풀이. 자석 문제 설명 \(N\)개의 폐구간에 대해, 각 구간 \(i\) (\(1 \le i \le N\))의 끝점 \(L[i]\), \(R[i]\)가 주어진다. 또한, 각 구간의 활성화 비용 \(W[i]\)가 주어진다. 하나의 구간 \(i\)를 비용 \(W[i]\)를 들여 활성화하면, 이 구간은 '활성구간'이 되고, 구간 \(i\) 및 구간 \(i\)와 한 점이라도 겹치는 모든 구간이 '커버'된다. 각 구간은 하나 이상의 구간에 의해 커버될 수 있다. 모든 구간을 커버하기 위한 최소 비용을 구하면? 제한조건: \(N \le 100,000\), \(0 \le L[i], R[i] \le 10^9\), \(1 \le W[i] \le 10^5\) 실행조건: 90개 이하 테스트 케이스에 대한 실행시간 총합 3초 이내 (자세.. 더보기
SCPC 2019 2차예선 풀이, 후기 SCPC 2차예선이 끝났다. 확실히 1차예선보다는 체감 난이도가 높았다. 1번 같은 경우에는 아이디어는 맞게 잡았는데 실수를 좀 했다. 점화식을 잘못 쓰거나 변수를 선언하고 초기화를 안 한다든지...하지만 제출횟수가 10번이라 다행이다!!ㅋㅋㅋ 4번은 휴리스틱이라 많이 어렵게 느껴졌는데 어떻게든 되지 않을까? 하는 심정으로 막 제출하다가 계속 안 돼서 각성하고 로컬에서 데이터 열심히 만들어서 확인해보고 만점을 받았다. 뭔가 데이터를 랜덤하게도 만들어 보고 절반만 빽빽하게 채워진 것도 만들어 보고 하면서 감을 잡았던 것 같다. 솔직히 이게 되려나... 하면서 제출했는데 만점이 뜬 문제ㅎㅎ 5번은 세그먼트 트리를 \(O(\lg{N})\)으로 구현해야 되는데 너무 오랜만이라 잘못 구현해서 \(O(N)\)이 되.. 더보기
SCPC 2017 본선 4번 풀이. 방 바꾸기 문제 설명www.codeground.org 참조 풀이, Part 1 (부분문제 2)원래 그래프를 G라고 하자. G에서 임의의 간선은 최대 하나의 사이클에만 속하므로, 사이클을 이루는 정점들을 하나로 묶은 그래프 T를 생각하자. 사이클을 이루지 않는 정점은 그대로 홀로 둔다. T는 트리가 된다. 왜냐면, T의 정점들이 사이클을 이룬다면 애초에 하나로 묶였을 것이기 때문이다. * 원래 그래프의 정점과 구분하기 위해 T의 정점과 간선은 슈퍼정점과 슈퍼간선으로 표현할 것이다.* INF = 무한대 (Infinity)의 약자로 쓸 것이다. T의 슈퍼정점들 중, 빈 방의 처음 위치를 포함하는 슈퍼정점이 딱 하나 있을 것이다. 이 슈퍼정점을 트리 T의 루트 R(T)로 하자. 빈 방은 R(T)의 자식슈퍼정점 중 일부를 .. 더보기
SCPC 2016 본선 3번 풀이. 폭격 문제 설명2차원 격자칸 형태의 적국에 폭격을 하려고 한다.격자칸의 가로 크기는 N, 세로 크기는 M 이다.좌표는 가장 왼쪽 위 칸을 (1 , 1)로, 가장 오른쪽 아래 칸을 (M,N)으로 표현한다.각 격자칸에 최대 하나의 목표물이 있으며, 전체 목표물의 개수는 P 로 주어진다.각 폭격기는 3X3크기의 영역에 있는 목표물을 모두 파괴할 수 있으며, 그 영역에 두 개 이상의 목표물이 있어야 출격이 가능하다고 한다.적국의 목표물 위치가 주어졌을 때 모든 목표물을 파괴할 수 있는 최소의 폭격기 수를 계산하라.두 개 이상의 폭격기가 하나의 목표를 파괴하는 것도 가능하다.아래 그림에서 왼쪽의 경우는 어떤 경우에도 한 폭격기는 하나의 목표만 파괴할 수 있어서 폭격이 불가능하다.오른쪽의 경우는 두 대의 폭격기가 출동하.. 더보기

티스토리툴바