[백준] 17484번 진우의 달 여행(Small) C++ 코드

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;
const int INF = 987654321;
int n, m, a[10][10], dp[10][10][4];

int go(int idx, int x, int dir) {
	if (x >= m || x < 0) return INF; // 벗어나면 최대값 반환
	if (idx == n) return 0; // 끝까지 가면 0 반환
	int &ret = dp[idx][x][dir];
	if (ret != -1) return ret; // 메모이제이션
	ret = 0;
	// 방향에 따라 다음 방향 결정
	if (dir == 1) {
		ret = min(go(idx + 1, x, 2), go(idx + 1, x + 1, 3)) + a[idx][x];
	}
	if (dir == 2) {
		ret = min(go(idx + 1, x - 1, 1), go(idx + 1, x + 1, 3)) + a[idx][x];
	}
	if (dir == 3) {
		ret = min(go(idx + 1, x - 1, 1), go(idx + 1, x, 2)) + a[idx][x];
	}
	return ret;
}

void FASTIO() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}

// dp배열은 [행][열][이동방향]으로 구성

int main() {
	FASTIO();
	cin >> n >> m;
    // 입출력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
    // dp배열 초기화
	fill(&dp[0][0][0], &dp[0][0][0] + 10 * 10 * 4, -1);
	int res = INF;
    // 인덱스 위치랑, 이동을 어떤 방향으로 할지 선택
	for (int i = 0; i < m; i++) {
		for (int j = 1; j < 4; j++) {
			res = min(res, go(0, i, j));
		}
	}
	cout << res << '\n';
	return 0;
}

풀이

dp를 써서 해결했다. dp배열은 행, 열, 이동방향으로 구성되었으며 처음 시작하는 열과 이동 방향을 모두 고려하여 최소값을 찾았다