17130번 토끼가 정보섬에 올라온 이유

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

다시 풀어볼 문제이다. 복습!

다이나믹 프로그래밍

난이도는 어려웠다.

다른 분의 코드를 참고하여 힌트를 얻어가며 구현하였다... 더 노력해야겠다.

배열의 크기가 크다.(예 : 1000 * 1000), 어느 한 쪽의 방향으로 가는 것 같다. 

→ dp(다이나믹 프로그래밍)인지 생각해 볼 것.

dp 배열도 -1로 초기화하는 것이 좋다. 

0으로 초기화하고,  토끼 위치를 1로하면 답을 출력할 때 ans - 1로 해야하는데

탈출을 못 할 때에는 -2가 돼버려, 또 다른 bool 같은 변수를 활용해야한다.

초기 나의 코드는 시간 초과코드이다.

1000 * 1000 배열을 재귀함수로 돌리니 당연히..

코드를 구현하는데 얻은 힌트를 첨부하겠다.

숫자는 순서라고 생각해도 된다. 한 쌍.

시간 초과 코드에서 핵심 부분

void simulation(int y, int x)
{
    int f = r(y, x);
    int s = ru(y, x);
    int t = rd(y, x);
 
    if (f != -1)
    {
        dp[y][x + 1] = max(dp[y][x + 1], dp[y][x] + f);
        simulation(y, x + 1);
    }
 
    if (s != -1)
    {
        dp[y - 1][x + 1] = max(dp[y - 1][x + 1], dp[y][x] + s);
        simulation(y - 1, x + 1);
    }
 
    if (t != -1)
    {
        dp[y + 1][x + 1] = max(dp[y + 1][x + 1], dp[y][x] + t);
        simulation(y + 1, x + 1);
    }
}

정답 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
char Map[1010][1010] = { 0, };
 
int R = 0, C = 0, ry = 0, rx = 0;
 
int dp[1010][1010] = { -1, };
 
int main(void)
{
    scanf("%d %d", &R, &C);
 
    for (int i = 0; i < R; i++)
    {
        scanf("%s", Map[i]);
 
        for (int j = 0; j < C; j++)
            if (Map[i][j] == 'R')
            {
                ry = i;
                rx = j;
                dp[ry][rx] = 0;
            }
            else dp[i][j] = -1;
    }
 
    int ans = -1;
 
    for (int x = rx + 1, sy = ry, ey = ry; x < C; x++)
    {
        if (sy - 1 >= 0) --sy;
        if (ey + 1 < R) ++ey;
 
        for (int y = sy; y <= ey; y++)
        {
            if (Map[y][x] == '#') continue;
            if (dp[y][x - 1] != -1) dp[y][x] = max(dp[y][x], dp[y][x - 1]);
            if (y - 1 >= 0 && dp[y - 1][x - 1] != -1) dp[y][x] = max(dp[y][x], dp[y - 1][x - 1]);
            if (y + 1 < R && dp[y + 1][x - 1] != -1) dp[y][x] = max(dp[y][x], dp[y + 1][x - 1]);
            if (Map[y][x] == 'C' && dp[y][x] != -1) ++dp[y][x];        
            if (Map[y][x] == 'O' && dp[y][x] != -1) ans = max(ans, dp[y][x]);
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}