dp2 [DP, DFS] 백준 1520 내리막길 C++ https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 : 일반적인 DFS로 풀었다가 시간초과나서 한참을 고민한 문제.. 결국 인터넷에서 풀이를 찾아봤는데 핵심은 DP를 쓰는 것이다 백트래킹인가 해서 삽질을 몇시간 했는데 결국 풀지 못함.. 결국 DP배열로 경로를 저장해두면 쉽게 풀린다. 경로를 저장한다는 개념이 좀 추상적인데 결국 map[0][0] 에서 map[m-1][n-1] 까지 가는 경로의 수를 구하는 문제 이므로 dp[i][j] 란 (i, j.. 2021. 8. 24. [DP] 백준 12865 평범한 배낭 C++ https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 처음 읽고 쉬워 보여서 2시간넘게 고민 했는데 풀지못했다.. 결국 풀이를 찾아 봤는데 knapsack알고리즘 이라고 꽤나 유명한 알고리즘이다. 나중에 알고리즘 관한 부분은 따로 정리해서 업로드 할 예정. 내가 생각하지 못한 솔루션은 무게 남을 때 어떻게 최댓값을 찾을 것인가(코드상으로 dp[i-1][j-weight])부분이었다. 천.. 2021. 8. 12. 이전 1 다음
