예제: 외발 뛰기
문제
땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다.균형을 잃어서 다른 발로 서거나 넘어져도 게임에서 집니다만, 재하와 영훈이는 젊고 활기차기 때문에 외발로 뛰어다니는 것은 아무것도 아닙니다. 다만 걱정되는 것은 주어진 게임판에 시작점에서 끝점으로 가는 방법이 존재하지 않을 수도 있다는 것입니다. 예를 들어 그림 (a)의 게임판에서는 사각형으로 표시된 칸들을 통해 끝에 도달할 수 있지만, 숫자가 하나 바뀐 그림 (b)에서는 그럴 수가 없습니다.
게임판이 주어질 때 왼쪽 위의 시작점에서 오른쪽 아래의 시작점에 도달할 수 있는 방법이 있는지 확인하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 격자의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에 각 n개의 숫자로 왼쪽 위부터 각 칸에 쓰인 숫자들이 주어집니다. 오른쪽 아래 있는 끝 점 위치에는 0이 주어집니다.출력
각 테스트 케이스마다 한 줄로, 시작점에서 끝 점으로 도달할 수 있을 경우 "YES"를, 아닐 경우 "NO"를 출력합니다. (따옴표 제외)예제 입력
2 7 2 5 1 6 1 4 1 6 1 1 2 2 9 3 7 2 3 2 1 3 1 1 1 3 1 7 1 2 4 1 2 3 4 1 2 3 3 1 2 3 4 1 1 5 2 9 4 7 0 7 2 5 1 6 1 4 1 6 1 1 2 2 9 3 7 2 3 2 1 3 1 1 1 3 1 7 1 2 4 1 2 3 4 1 3 3 3 1 2 3 4 1 1 5 2 9 4 7 0예제 출력
YES NO
풀이
동적 계획법 문제이다. 문제를 작게 나눌 수 있으면 동적 계획법을 적용할 수 있다고 하는데, 이 문제 또한 그러하다. (y, x) 좌표에서 목표까지 이동할 수 있느냐 여부로 나눌 수 있겠다.
풀이법은 크게 복잡하지 않다.
기저사례는 y, x 좌표가 맵을 벗어나면 0(실패), y == x == n - 1이면 1(성공)을 return하게 하고,
기저사례가 아닐 경우는 (y, x)좌표 크기만큼 아래 또는 오른쪽으로 이동하면 된다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<cstring>
using namespace std;
int n;
int map[100][100];
int cache[100][100];
int goal(int y, int x) {
if (y >= n || x >= n) return 0;
if (y == n - 1 && x == n - 1) return 1;
int& res = cache[y][x];
if (res != -1) return res;
int len = map[y][x];
return res = (goal(y + len, x) || goal(y, x + len));
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
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];
}
}
cout << (goal(0, 0) == 1 ? "YES" : "NO") << endl;
}
return 0;
}풀이 후기
필자는 처음에 오답에 막혔는데, 틀린게 없는데 뭘까.. 했더니
res = (goal(y + len, x) || goal(y, x + len));
이 부분을
res = (goal(y + len, x) + goal(y, x + len));
이렇게 했었다.
로직으로는 문제가 없지만, 입력이 커지면 overflow가 날 수 있다고 한다.
생각해보면, 입력이 최대인 100에 모든 블럭의 값이 1이면 그 크기가 엄청나질 것 같다.
그러니 문제를 잘 읽어보고, 문제가 원하는 답만 간결하게 찾아낼 수 있도록 함수를 구성하는것도 아주 중요한 것 같다😁
