백준14 백준 욕심쟁이판다 (Python/Go) 문제 링크: www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 단순히 bfs로 완전탐색하면 시간초과가 나기 때문에 dfs+dp로 풀어야하는 난이도 있는 문제입니다. 핵심은 2차원 dp를 만들어서 dp에 0이 아닌 값이 있다면 탐색을 그만하고 그 값을 사용하면 됩니다. 예를 들어 (2, 2)에서 출발하였고 위로 1칸 갔다고 가정해본다면 (1, 2) 좌표입니다. dp[1][2] = 3 이런식으로 값이 저장되어 있다면 더 이상 탐색을 그만하고 3 + 1 값.. 2021. 3. 31. 백준 12865번 1차원 리스트 풀이(파이썬) 문제 링크: www.acmicpc.net/problem/12865 유명한 dp문제인 knapsack 문제입니다. 굳이 2차원 배열을 사용하지 않아도 1차원 리스트로 덮어 쓰면 풀이가 가능합니다. 이 문제는 각 물건을 1번씩 밖에 사용하지 못하므로 1차원 리스트로 풀이할 경우 거꾸로 탐색하면서 풀어야 각 물건을 1번씩만 사용하게 됩니다. 왜 거꾸로 해야하는지는 한번 생각해보시길 바랍니다. 2021. 3. 26. 이전 1 2 3 4 다음
