11048
-
백준(BOJ) 11048번 이동하기알고리즘 풀이/백준(Boj) 2019. 7. 3. 22:16
문제: https://www.acmicpc.net/problem/11048 입력첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.출력첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다. 나의풀이 :완전탐색의 경우 탐색했던 경로를 또 탐색해야 하니 시간초과가 되었고 따라서 각 부분 문제를 최적으로 풀고 그 결과를 cache에 저장해 둠으로써 경로의 중복을 없앴다. 완전탐색 #include #include using namespace std;const int MAX = ..