글 읽기 - 문제를 풀고도 잘 이해가 안가는 부분이 있네요ㅠㅠ 도와주세요 고수님들

doubleknd26 7년 전 0

이 문제의 점화식을

D[x][y][l][k] =

x,y지점에서N,M까지 갈 때,

이 지점을 방문하기 전 들른 오락실이 l번째 오락실일 경우,

이 지점부터 오락실을 k번 지나가는 경우의 수.

이렇게 점화식을 세웠습니다.

궁금한 점은 l을 왜 메모이제이션 해줘야 하는가 입니다.

l은 해당 지점을 방문하기 전에 들른 오락실의 번호인데,

예를 들어 현재 지점이 5번 오락실일 경우에 이 지점을 방문하기 전에 방문한 오락실이 만약 1, 2, 3, 4 (즉 5보다 작으면) 다 똑같은 값을 갖는다고 생각해서

전에 방문한 지점 값을 메모이제이션 하지 않고 파라미터로 값을 넘기고 그 값보다 현재 방문한 오락실 번호(5)가 큰지 작은지만 확인해주면 될거라고 생각했는데 그렇지 않더라구요..

왜 그런가요 ??ㅠㅠ

#include <cstdio>
#include <vector>
#define SIZE 51
#define MOD 1000007
using namespace std;

int n, m;
int cache[SIZE][SIZE][SIZE][SIZE];
vector< pair<int, int> > v; // 오락실 순서대로 위치 저장
vector<int> ans;

int dp (int x, int y, int l, int k) {
    
    int len = (int)v.size();
    
    if (x<1 || x>n || y<1 || y>m) return 0;
    
    if (x==n && y==m) {
        for (int i=1 ; i<len ; i++) {
            if (v[i].first == x && v[i].second == y) {
                if (k==1 && l<i) {
                    return 1;
                }
                else {
                    return 0;
                }
            }
        }
        if (k==0) return 1;
        else return 0;
    }
    
    int &ret = cache[x][y][l][k];
    if (ret!=-1) return ret;
    
    ret = 0;
    for (int i=1 ; i<len ; i++) {
        //현재 위치가 오락실인 경우.
        if (v[i].first == x && v[i].second == y) {
            if (k>0 && l<i) {
                return ret = ( (dp(x+1, y, i, k-1)%MOD) + (dp(x, y+1, i, k-1)%MOD) ) % MOD;
            }
            else {
                return ret;
            }
        }
    }
    // 현재 위치가 오락실이 아닌 경우.
    return ret = ( (dp(x+1, y, l, k)%MOD) + (dp(x, y+1, l, k)%MOD) ) % MOD;
}

int main () {
 
    int c, x, y;
    
    scanf ("%d %d %d", &n, &m, &c);
    
    v.push_back(make_pair(0, 0));   // 0번지에 초기값 지정.
    for (int i=1 ; i<=c ; i++) {
        scanf ("%d %d", &x, &y); v.push_back(make_pair(x, y));  // 1번 오락실부터 1번지에 들어감.
    }
    
    // 캐시 초기화.
    for(int i=0 ; i<SIZE ; i++)for(int j=0 ; j<SIZE ; j++)for(int l=0 ; l<SIZE ; l++)for(int k=0 ; k<SIZE ; k++)
        cache[i][j][l][k] = -1;
    
    for (int i=0 ; i<=c ; i++) ans.push_back ( dp (1, 1, 0, i) );
    
    for (int i=0 ; i<ans.size() ; i++) printf ("%d ", ans[i]);
    printf ("\n");
    
    return 0;
}

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

문제

문제

출처

ICPC

문제를 풀고도 잘 이해가 안가는 부분이 있네요ㅠㅠ 도와주세요 고수님들

doubleknd26 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말