백준 17485 진우의 달 여행 (Large) 혼내주기
완전탐색 + dp 문제. 시작점에서는 모든 방향으로 움직일 수 있기 때문에 이중 for문으로 출발점을 일일이 찍어주면 방향 때문에 dp 배열 크기를 4로 하지 않아도 된다. 이 문제를 풀면 17484 진우의 달 여행 (Small) 문제를 날로 먹을 수 있다. #include #include #include using namespace std; int dy[3] = {-1, 0, 1}; int map[1000][1000], cache[1000][1000][3]; int n, m; int d(int x, int y, int dir){ if(x == n) return 0; int& ret = cache[x][y][dir]; if(ret != -1) return ret; ret = 1e9; for(int i =..
혼내주기
2021. 8. 1. 23:24