-
[BOJ]백준 22114번: 창영이와 점프(C++)/DPProblem Solving/BOJ(백준) 2021. 8. 8. 13:56
https://www.acmicpc.net/problem/22114
오랜만에 푸는 DP문제
처음에 bottom-up으로 풀려고 했는데 점화식이 계속 생각이 안 나서 재귀로 푼 다음에 메모이제이션 적용했다
dp도 재귀(top-down)이기 때문에 base case, inductive step, memoization 이 세 가지 위주로 설계해야 할 듯
#include <cstdio> #include <algorithm> using namespace std; int n, k, l[100005], dp[2][100005],ans; int func(bool b, int cur) { if (cur == n)return 1; int& ret = dp[b][cur]; if (ret != -1)return ret; ret = 1; if (l[cur] <= k) ret = func(b, cur + 1) + 1; else if (!b) ret = max(func(true, cur + 1) + 1, ret); return ret; } int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &l[i]); fill(&dp[0][0], &dp[1][100001], -1); dp[0][n] = dp[1][n] = 1; for (int i = 1; i <= n; i++) ans = max(ans, func(false, i)); printf("%d", ans); return 0; }
'Problem Solving > BOJ(백준)' 카테고리의 다른 글
[BOJ]백준 1495번: 기타리스트(C++)/DP (175) 2021.08.15 [BOJ]백준 20160번: 야쿠르트 아줌마 야쿠르트 주세요(C++)/Dijkstra (0) 2021.08.09 [BOJ]백준 22352번: 항체 인식(Python)/BFS (0) 2021.08.04 [BOJ]백준 20304번: 비밀번호 제작(Python)/Bitmask, BFS (477) 2021.08.04 [BOJ]백준 20058번: 마법사 상어와 파이어스톰(C++)/Simulation (0) 2021.07.31