3~4월 첫 복기는 풀었던 문제 중 기억나는 DP류 문제만 복기한다.
개인적인 복기용이므로 가독성이나 남들이 이해할수 있는가 등등은 아예 신경 안썼다. 아마 나만 알아볼듯.
풀이가 대놓고 적혀있기 때문에 스포를 주의한다.
21343. Great Expectation (D4 / nwerc 2020 G) ★★
리셋이라는 기능을 DP식에 잘 녹일 수 있을까? 를 묻는 문제.
DP임을 눈치채기는 쉬우나 점화식을 만드는 것이 상당히 까다롭다.
1) 기대값을 DP에 어떻게 담는가?
2) 리셋을 DP에 어떻게 담는가?
3) DP 갱신을 파라매트릭 서치로 할 수 있는가?
세가지의 중요한 관찰포인트가 있고 셋 다 처음 봤다. 너무 의미있는 문제였음. 여기 적혀있는 하나씩만 해도 굉장한데 그 많은걸 한 문제에 다 녹여냈기 때문에 더 좋았다. 강추
25994. Crashing Competition Computer (P5 / bapc 2022 C)
윗 문제의 3단 열화 버전.
1) 기대값을 DP에 어떻게 담는가?
위에서의 요지 중 가장 쉬운 관찰포인트에 해당한다. 그조차도 힌트가 많아서 더 찾기 쉬운편. 이전 문제를 푼 뒤에 이 문제를 풀게 돼서 그런가 더 쉽게 느껴졌다. 복습용으로 굿이였다
26969. Bribing Friends (P2 / usaco 2022 dec gold 1) ★★
매우 흥미로운 정통 DP 문제.
1) DP에 greedy한 전략이 있을 때 무엇을 할 수 있는가?
2) DP식의 시간복잡도를 줄이기 위해서는 무엇을 해야 하는가?
여러 의미로 아주 도움이 많이 된 문제다. 이것도 강추
24488. Drought (P3 / usaco 2022 jan gold 1) ★
이것도 무난무난한 DP문제이다. 근데 못풀었다..
1) 총 가짓수를 구하라고 했을 때 뭘 할수 있을까?
2) DP 갱신의 시간복잡도를 어떻게 줄일 수 있을까?
기본적인 문제인 것 같은데 아직 경험이 부족한 것 같다. 꼭 완벽히 다지고 넘어가야 할 문제 중 하나라고 생각한다.
27556. Lights Off (P2 / usaco 2023 jan gold 2) ★
관찰을 기반으로 한 전처리 DP 문제.
1) 여러 쿼리가 주어지는데 모든 쿼리에 똑같은 공통점이 있을때, 어떻게 활용해야 할까?
2) 기존의 값이 지속적으로 진행될 경우 이를 수식적으로 어떻게 표현할 수 있을까?
관찰이 메인인 코포틱한 문제. 2400급에 나올법한 문제였다. 구현도 생각보다 까다롭고 문제가 되게 좋다.
12013. 248 game (G5 / usaco 2016 open gold 3)
전형적인 구간 쿼리 문제.
1) 합친다는 개념을 어떻게 정의하는 것이 좋을까?
풀이 단박에 떠오르지는 않았다. 그래서 한번 더 복기하려고 들고왔다. 좋은 dp문제라고 생각한다.
23872. Paired Up (P2 / usaco 2021 dec gold 1) ★
1차원 좌표계에서의 DP 문제.
1) 1차원 좌표만이 가지는 특징은 무엇이 있을까?
2) pair가 있을 때의 최선의 전략과 그를 기반으로 할 수 있는 것은 무엇이 있을까?
3) 식의 관리는 어떻게 하는게 좋을까?
대부분의 관찰들이 매우 의미있다고 생각한다. 좋은 문제. 아직 못맞춰서 꼭 풀어봐야 한다.
20645. Bovine Genetics (P1 / usaco 2020 dec gold 2) ★★
아주 좋은 정통 DP문제.
1) ? 연산자를 DP에서 어떻게 이용할 수 있을까?
2) DP식은 어떻게 세우는 것이 올바른가?
정통 문제인데 아직도 못풀었다. 꼭 풀어볼 생각임.
21230. Moder Art 3 (P2 / usaco 2021 feb gold 2) ★
매우 신기한 구간 DP문제.
1) base를 어떻게 관리하는 것이 좋을까?
2) 어떤 원리로 구간DP의 식을 정의할 수 있을까?
여러번 다시 읽어보고 다시 곱씹어볼 필요가 있는 문제라고 생각한다.
15759. Talent Show (P3 / usaco 2018 open gold 3)
무난무난한 DP문제.
1) DP 내에서 그리디한 전략이 존재할 때, 어떻게 활용하는 것이 좋을까?
2) 여러 가지 경우의 수로 분기되어 있을 경우 어떻게 접근하는 것이 좋을까?
무난한 DP 기본형 문제라고 생각한다. 기본을 다지자!
27234. 컵 쌓기 (P2 / hello boj 2023 D) ★
구간 DP 경우의수 문제.
1) 구간 DP를 통해 경우의 수를 셀 때, 중복되어 세지 않도록 어떻게 관리해야 할까?
경우의 수를 구하는 구간DP의 가장 일반적인 문제라고 생각한다. 한번쯤은 풀어봐야 한다고 생각함.
div1 850-D. Wooden Spoon (2400) ★★
토너먼트 상에서의 DP문제.
꼭 풀어볼 생각이다.
div1+2 844-F. Bracket Insertion (2700) ★
괄호 속에서의 DP문제.
꼭 풀어볼 생각이다.
25998. Grinding Gravel (D5 / bapc 2022 G) ★★
전혀 DP로 보이지 않았던 np처럼 생긴 문제.
1) n = 100 내외일때, 다항시간에 문제를 풀기 위해 어떤 접근을 하는 것이 좋을까?
2) DP로 변환하기 위해서는 어떤 조건이 필요한가?
개인적으로 되게 신기했다. 아주 좋은 문제라고 생각한다.