BOJ16174

02 Feb 2020 • ProblemSolving

점프왕젤리(Large)

문제출처

문제 해석

  • 젤리가 (0,0)에서 출발해서 (N-1,M-1)에 도달할 수 있는 지 판단하는 문제입니다.

  • 다음과 같은 조건으로 게임이 진행됩니다.

    1. 정사각형 구역 내부에서만 움직일 수 있고, 외부로 나가는 경우는 패배합니다.
    2. 젤리의 출발점은 (0,0)이며 오른쪽 또는 아래로만 이동할 수 있습니다.
    3. 현재 밟고 있는 칸에 쓰여있는 수만큼 이동해야 합니다. (초과 또는 미만으로 이동할 수 없습니다)
    4. (N-1, M-1)에 도달 시 종료합니다.

설계(10)

  • 단순 dp문제로 구현하였습니다.
  • 오른쪽으로 가는 경우와 아래로 가는 경우를 모두 구하기 위해 cache[x][y][오른쪽 or 아래] 배열을 사용하였습니다.
  • x == N-1 && y == N-1 인 경우 1을 return 하게 구현 하였습니다.

구현(5)

코드
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 64

int map[MAXN][MAXN];
int cache[MAXN][MAXN][2];

int N;
int dp(int x, int y, int dir) {
	if (x == N - 1 && y == N - 1) return 1;
	int& ret = cache[x][y][dir];
	if (ret != -1) return ret;
	ret = 0;
	if (x + map[x][y] < N) ret = max(ret,dp(x + map[x][y], y, 1));
	if (y + map[x][y] < N) ret = max(ret,dp(x, y + map[x][y], 0));
	return ret;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	int ans = dp(0, 0, 0);
	if (ans) cout << "HaruHaru\n";
	else cout << "Hing\n";
	return 0;
}
디버깅
제출결과
  • 0ms

마무리

  • 다른 분들의 공개된 코드를 참조해보면 맵을 순차적으로 돌면서 이동할 수 있는 좌표를 체크하는 방식으로 구현하였습니다.
  • 이 방법이 훨씬 가독성이 좋고 깔끔한 것 같습니다.
 BOJ

Related Posts