DP2 [ PS ] 백준 1823, 수확 백준 1823번: 벼 선택문제 정보문제 번호: BOJ 1823문제 이름: 벼 선택난이도: Gold문제 링크: https://www.acmicpc.net/problem/1823문제 요약N개의 벼가 주어진다.벼를 왼쪽과 오른쪽에서 하나씩 선택하면서, 그 선택된 벼의 점수는 현재 선택된 벼의 가치 * (현재 턴) 으로 계산된다.매번 왼쪽 끝 벼나 오른쪽 끝 벼를 선택할 수 있다.벼를 모두 선택할 때, 얻을 수 있는 최댓값을 구하는 문제이다.처음 떠올린 아이디어처음에 문제를 봤을 때, 그리디 알고리즘을 사용할 수 있을 것 같았지만, 최적의 선택을 할 때마다 다른 선택이 영향을 미치기 때문에 완전 탐색이나 DP를 고려하게 되었다.벼를 하나씩 선택하면서 점수를 누적하는 방식이므로 DP 방식으로 해결할 수 있을 것 .. 2026. 4. 8. [ PS ] 백준 25759, 들판 건너가기 문제 정보문제 번호: BOJ 25759문제 이름: 들판 건너가기난이도: Gold문제 링크: https://www.acmicpc.net/problem/25759문제 요약꽃의 개수 N이 주어진다.N개의 나열된 꽃 중에서, "인접한 꽃의 아름다움 차이"가 최대가 되도록 최적해를 찾는다.처음 떠올린 아이디어처음에는 DFS를 통해서, 분기 처리를 통해 구현할 수 있다고 생각했다. DFS로 구현하고 보니, DP로 뺄 수 있을 것 같아서 메모이제이션만 섞어서 Top-Down 방식으로 변경했다.핵심 포인트Top-Down 방식으로 수행할 때, 퓨어 펑션을 만들기 위해 어떠한 인자를 들고 갈 것인지 정해야 한다.점화식을 어떻게 세울 것인가? => 경우는 꽃의 갯수를 벗어나거나 이미 계산된 값이 있을 경우이다.solve(p.. 2026. 4. 8. 이전 1 다음