글 읽기 - dp로 풀었는데 궁금한점이 있습니다.

tkdwo7699 1년 전 0

제가 생각했던 풀이는 한 칸에서 상하좌우마다 받아온 경로를 따로 저장하고 이를 반복해서 구하는 dp였는데요

제가 주석처리한 부분처럼 dp부분을 반복하는 횟수가 왜 5번이 되어야 맞는지 궁금합니다.

데이터셋이 약한것일수도 있다는 생각이들고 아니면 5번까지인 이유가 있다는 생각도 듭니다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<map>
#include<stack>
#include<queue>
#include<set>
using namespace std;
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
int arr[500][500];
int dp[500][500][4];
int main(){
    int N,M;
    scanf("%i%i",&N,&M);
    for(int x=0;x<N;x++){
        for(int y=0;y<M;y++) scanf("%i",&arr[x][y]);
    }
    dp[0][0][0]=1;
    for(int i=0;i<5;i++){ #이 부분
        for(int x=0;x<N;x++){
            for(int y=0;y<M;y++){
                for(int z=0;z<4;z++){
                    int cx=dir[z][0]+x;
                    int cy=dir[z][1]+y;
                    if(cx<0 || cy<0 || cx>=N || cy>=M) continue;
                    if(arr[x][y]>=arr[cx][cy]) continue;
                    int temp=0;
                    for(int w=0;w<4;w++){
                        if(z>=2 && w==z-2) continue;
                        if(z<2 && w==z+2) continue;
                        temp+=dp[cx][cy][w];
                    }
                    dp[x][y][z]=temp;
                }
            }
        }
    }
    int solve=0;
    for(int x=0;x<4;x++) solve+=dp[N-1][M-1][x];
    printf("%i",solve);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dp로 풀었는데 궁금한점이 있습니다.

tkdwo7699 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말