[틀림] 백준 1513 경로찾기 // 4차원 dp, 경로찾기 dp , 경우의수 dp

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

* 시도1

• 한번에 탐색후
• dp[y][x][오락실cnt]로 출력하면?

• 문제점
  • else if 남발
  • 보다는 종료조건 사용할것
  • ret+=가 아니라 ret = ( 좌dfs + 우 dfs) 형태가 맞음.
    • 트리그린후, 재귀로 이해

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

int n, m, c;
int a[54][54];
ll dp[54][54][54]; // y, x, 오락실 번호: 경우의 수
const int mod = 10000007;

ll dfs(int y, int x, int cnt) {
   if(y <= 0 || x <= 0 || y > n || x > m) {
      return 0; // 범위 밖
   }
   if(y == n && x == m) {
      return 1; // 목적지 도달
   }

   ll& ret = dp[y][x][cnt];
   if(ret != -1) {
      return ret; // 이미 계산됨
   }

   ret = 0;
   if(a[y][x] == 0) { // 오락실이 아닌 경우
      // 아래로 이동 시도
      if(y + 1 <= n) {
         if(a[y+1][x] == 0) {
            ret = (ret + dfs(y+1, x, cnt)) % mod;
         } else {
            ret = (ret + dfs(y+1, x, cnt+1)) % mod;
         }
      }
      
      // 오른쪽으로 이동 시도
      if(x + 1 <= m) {
         if(a[y][x+1] == 0) {
            ret = (ret + dfs(y, x+1, cnt)) % mod;
         } else {
            ret = (ret + dfs(y, x+1, cnt+1)) % mod;
         }
      }
   } else { // 현재 위치가 오락실인 경우
      // 아래로 이동 시도 (오락실 번호가 더 큰 경우만)
      if(y + 1 <= n && a[y+1][x] > a[y][x]) {
         ret = (ret + dfs(y+1, x, cnt+1)) % mod;
      }
      
      // 오른쪽으로 이동 시도 (오락실 번호가 더 큰 경우만)
      if(x + 1 <= m && a[y][x+1] > a[y][x]) {
         ret = (ret + dfs(y, x+1, cnt+1)) % mod;
      }
   }
   
   return ret;
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   memset(dp, -1, sizeof(dp));
   cin >> n >> m >> c;
   
   int cnt = 1;
   for(int i = 0; i < c; ++i) {
      int y, x;
      cin >> y >> x;
      a[y][x] = cnt;
      cnt++;
   }
   
   dfs(1, 1, a[1][1] > 0 ? 1 : 0); // (1,1)이 오락실이면 1, 아니면 0으로 시작
   
   for(int i = 0; i <= c; ++i) {
      cout << dp[n][m][i] << " ";
   }
   
   return 0;
}

 

* 경우의수 dp

• 올바른경로 -> return 1
• 배제경로 -> return 0
• ret = ( 상 + 하 + 좌 + 우)

 

 

* 풀이

• cnt는 0부터 시작해서 증가보다, 가야하는 값을 크게준후 , 감소시키는게 유리

ll dp[54][54][54][54]; //y,x,방문해야하는오락실수, 마지막으로방문한오락실번호 : 그때, 경우의수

• y,x 가 뭔지몰라서, 검사하는 방식으로 생각
• y,x는 검사해야하는 미래값임

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

int n,m,c;
int a[54][54];
ll dp[54][54][54][54]; //y,x,방문해야하는오락실수, 마지막으로방문한오락실번호 : 그때, 경우의수
const int mod=1000007;

ll dfs(int y, int x, int cnt, int prev) {
   if(y <=0 || x<=0 || y>n || x>m ) {
      return 0; //배제
   }
   if(y==n && x==m) {
      if(cnt==0 && a[y][x]==0) {
         return 1;
      }
      if(cnt==1 && a[y][x] > prev) {
         return 1;
      }
      return 0; //그외는 유효하지않은 경로, 배제
   }

   ll & ret = dp[y][x][cnt][prev];
   if(ret!=-1) {
      return ret % mod;
   }

   ret=0; //리프노드 시작 리턴값
   // 현재 위치가 빈 칸인 경우
   if(a[y][x]==0) {
      // 아래쪽과 오른쪽으로 이동하는 경우의 수를 더함 (상태 변화 없음)
      ret=(dfs(y+1,x,cnt,prev) + dfs(y,x+1,cnt,prev))%mod;
   }
   // 현재 위치가 오락실이고, 이전 오락실보다 번호가 큰 경우
   else if(a[y][x]>prev){
      ret=(dfs(y+1,x,cnt-1,a[y][x]) + dfs(y,x+1,cnt-1,a[y][x]))%mod;
   }
   // 오락실이지만 이전 오락실보다 번호가 작은 경우는 유효하지 않으므로 ret = 0 유지
   
   return ret % mod;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   memset(dp,-1,sizeof(dp));
   cin>>n>>m>>c;
   int cnt=1;
   for(int i=0;i<c;++i) {
      int y,x;
      cin>>y>>x;
      a[y][x]=cnt;
      cnt++;
   }
   for(int i=0;i<=c;++i) {
      cout<<dfs(1,1,i,0)<<" ";
   }
}