백준 2169번 로봇 조종하기

https://www.acmicpc.net/problem/2169

2169번: 로봇 조종하기

 

 

 

 

<접근방법>

dp 문제입니다.

dp 하수 오브 하수라서 못풀었습니다..ㅠㅠ

 

cache 배열은 중복계산을 방지하기 위해 메모이제이션을 하는 배열입니다.

이 배열이 왜 3차원 배열이 되어야 하는가에 대해 이해가 잘안갔습니다.

 

그 이유는 (y, x)에 도달할 때, 도달하는 방향에 따라 값이 달라질 수 있고

그에 따라 메모이제이션도 달리 해야하기 때문입니다.

 

댓글에 자세한 예시와 함께 설명이 있습니다.

제가 물어봤습니다. 헤헤

https://100100e.tistory.com/189

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

const int INF = 1000000;
int n, m;
int map[1001][1001], cache[1001][1001][3];
bool visit[1001][1001];
int dy[3] = { 1, 0, 0 };
int dx[3] = { 0, 1, -1 };

int dfs(int y, int x, int dir) {
	//기저사례
	if (y == n-1 && x == m-1) return map[y][x];

	int &res = cache[y][x][dir];
	if (res != -INF) return res;

	for (int i = 0; i < 3; i++) {
		int ty = y + dy[i];
		int tx = x + dx[i];

		if (ty < 0 || ty >= n || tx < 0 || tx >= m || visit[ty][tx]) continue;

		visit[ty][tx] = true;
		res = max(res, dfs(ty, tx, i) + map[y][x]);
		visit[ty][tx] = false;
	}
	return res;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			cache[i][j][0] = cache[i][j][1] = cache[i][j][2] = -INF;
		}
	}

	visit[0][0] = true;
	cout << dfs(0, 0, 0) << '\n';

	return 0;
}

 

 

---

 

 

<느낀 점>