알고리즘 /Dynamic Programming (6) 썸네일형 리스트형 [백준] 로봇 조종하기_2169 cache[y][x] = 현재 위치에서 앞으로 더 얻을 수 있는 최대 가치 이렇게 두고 풀었는데, 저 테스트케이스를 통과하지 못해서 계속 틀렸다. cache를 방향까지 고려해서 3차원 배열로 해야한다는 것을 미처 생각하지 못했다. 7이 나와버림.. 4 4 1 1 1 1 -1 -1 -1 1 1 1 1 1 100 -10 1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 100 -10 1 1 최대 가치(101)를 얻으려면 이렇게 움직여야 한다. 현재 위치에서 앞으로 더 얻을 수 있는 가치는 그 전 방향에 따라 다르다. 따라서 위치 + 방향까지 고려해서 3차원 배열을 사용해야 한다. 왼쪽에서부터 왔다면 다시 왼쪽으로는 못 갈테니깐, 다른 방향으로 가서 최댓값을 저장하게 된다. 하지만 다른 방향에서 왔다면 .. [백준] 연속합_1912 기초 dp 문제들 중에 안 푼게 꽤 있길래 다시 풀고 있다... 히히.. 숫자는 어차피 연속적으로 더해야 하므로 바로 전 숫자만 고려하면 된다. cache[i] = max(arr[i], arr[i] + cache[i - 1]); 지금 내 숫자(arr[i])에 그 전까지 연속적으로 더해왔던 숫자 합(cache[i-1]을 더해서 손해가 난다면 이 합을 더할 필요가 없다. 연속을 끊고 cache에는 지금 숫자만 저장하면 된다. **몰랐던 것 잘 가다가 틀려서 왜 틀렸을까 생각해봤는데 최댓값을 업데이트하는 for문 부분을 i=1 인덱스에서부터 시작하게 했기 때문에, 숫자가 하나만 들어오는 경우에는 최댓값을 업데이트하지 못해 틀린 것이었다. 그래서 숫자가 1개인 경우에는 그 숫자가 최댓값이 되도록 설정하고, 나머.. [백준] 정수 삼각형_1932 그 위치에서 선택할 수 있는 수의 최대의 합을 cache에 저장하면서 배열의 끝까지 내려가는 dfs이다. 결국 dfs가 모두 끝난 뒤에는 0,0 위치에서 구할 수 있는 최대의 합이 나온다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include using namespace std; int n; int tr[500][500]; int cache[500][500]; int ans = 0; int max(int a, int b) { return a > b ? a : b; } int dfs(int y, int x) { if (y == n) return 0; int& ret = ca.. [백준] 퇴사_14501 판다 문제와 많이 유사해서 금방 풀 수 있을거라고 생각했는데, 생각보다 시간이 오래 걸렸다. 오늘 들어온 상담까지 끝내고 난 뒤의 날짜와, 이렇게 상담을 끝내고 다음 상담을 시작할 수 있는 날짜를 혼동했기 때문이다. ret = -1이라면 이미 계산된 값이므로 그냥 이 값을 반환한다. 일이 끝나는 날짜(nd-1)가 n보다 크다면 이 일은 못 끝내므로 그냥 0을 반환한다. 이 경우가 아니라 n일까지 일을 끝낼 수 있다면 ret에 해당 상담를 통해 벌 수 있는 돈을 저장한다. 이 상담을 끝낸 이후 또 일을 할 수 있다면 이 일은 nd일부터 시작할 수 있을 것이고, 남은 상담들은 for문을 통해 dfs를 타고가면서 최대값을 ret에 업데이트한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 .. [백준] 욕심쟁이 판다_1937 중복 계산을 막기 위해 cache 리스트를 만들어 이미 계산한 값을 저장해둔다. 어떤 위치에서 판다가 오래 삼을 수 있다는 말은 조건에 맞게 dfs를 타고 갈 수 있는 경로도 길다는 뜻이다. 경로를 맞게 타고 갈 때마다 그 위치에서 또 갈 수 있는 경로를 탐색한다. 만약 어떤 위치에서 갈 수 있는 경로가 아예 없다면 ret은 1인채로 반환이 될 것이고, 이것은 그 위치에서 팬더가 하루밖에 못 산다는 것을 의미한다. 갈 수 있는 경로가 두 개 더 있는 상태라면? ret = max(ret,panda(ny, nx)+1); dfs를 따라 갔을 때 더 갈 수 있는 경로가 있으므로 ret = max(ret,panda(ny, nx)+1); 가 또 호출된다. 세번째 실행되는 dfs 함수에서는, 여기서 또 갈 수 있는 .. [알고리즘 문제해결전략] 동적 계획법 예시 jump 가장 기본적인 형태 중 하나이다. 1. 주어진 문제를 완전 탐색을 이용해 해결한다. 2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용한다. 1 2 3 4 5 6 7 8 9 10 11 12 int n, board[100][100]; int cache[100][100]; int jump2(int y, int x) { if (y >= n || x >= n) return 0; //기저사례 처리 if (y == n - 1 && x == n - 1) return 1; //끝에 도달 //메모이제이션 int& ret = cache[y][x]; //이미 계산된 값이라면 그 값을 반환 if (ret != -1) return ret; int jumpsize = board[y][x]; return ret = (.. 이전 1 다음