[백준 20971] No Time to Paint
문제 www.acmicpc.net/problem/20971 알고리즘 DP 풀이 특정 구간을 칠하지 않은 상태로 할 때, 남은 구간들을 칠하기 위한 최솟값을 구하는 문제입니다. 문제의 가장 큰 특징은 페인트를 칠하는 순서가 정해져 있다는 것입니다. 이를 유의하며 풀도록 합시다. 쿼리를 빠르게 처리하기 위해 DP 아이디어를 떠올렸습니다. 특정 구간에 대한 DP를 사용하기 위해선 $cache[i][j]$와 같은 배열을 사용할 수 있는데, 구간의 길이가 100,000 이라는 점에서 해당 2차원 배열을 사용하기는 어렵습니다. 하지만 문제를 자세히 보면 특정 구간을 칠하기 위한 최솟값이 아닌 특정 구간을 제외한 나머지 구간을 칠하기 위한 최솟값을 묻고 있습니다. 이는 DP의 정의가 "앞에서부터 길이 $N$인 구간을..
Algorithm
2021. 4. 30. 12:37
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- SCC
- 세그먼트트리
- implementation
- greedy
- Fenwick
- sorting
- Oracle
- 트라이
- dijkstra
- string
- knapsack
- Suffix Array
- union find
- kmp
- DP
- sweeping
- bfs
- spring
- spring boot
- 이분매칭
- 좌표압축
- Segment tree
- 스위핑
- 동적계획법
- 펜윅트리
- dfs
- hld
- 정렬
- 이분탐색
- 2-SAT
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 |
글 보관함