JUMPGAME [오답,C++]

  • ssy10011218
    ssy10011218

    아이디어

    동적 프로그래밍으로 풀었고 오답이 납니다...
    그래서 문제해결전략 책에있는 solve()함수를 참조해서 다시 짜보았는데도 오답이 납니다.

    우선 기저사례는 판을 벗어난 경우에는 거짓(0) 도착한 경우에는 참(1)을 반환하도록 하였고 처음에 판을 -1로 초기화 하였습니다.
    그 다음 ret값이 계속변하면서 메모이제이션 배열에 저장할 수 있도록

    int &ret = d[x][y];

    이런식으로 하고

    return ret=(solve(x+step,y)||solve(x,y+step));

    다음과 같이 오른쪽과 아래로 가는 함수를 호출하는 동시에 이것들이 가지는 값이 참인지 아닌지 확인해보았습니다.

    소스코드

    #include <stdio.h>
#include <cstring>
using namespace std;
int c;
int n;
int a[101][101];
int d[101][101];

int solve(int x, int y){
  //base::case
  if(x>=n || y>=n) return 0;
  if(x==n-1 && y==n-1) return 1;

  int &ret = d[x][y];
  if(ret!=-1) return ret;
  int step = a[x][y];
  return ret=(solve(x+step,y)||solve(x,y+step));
}

int main(){
  memset(d,-1,sizeof(d));
  scanf("%d",&c);
  while(c--){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
      for(int j=0; j<n; j++) scanf("%d",&a[i][j]);    
    }
    if(solve(0,0)) printf("YES\n");
    else printf("NO\n");
  }
  return 0;
}

    7년 전
1개의 댓글이 있습니다.
  • Corea
    Corea

    d 배열의 초기화를 각각의 테스트 케이스마다 해주어야 합니다. 새로운 테스트 케이스를 받으면 그 테스트 케이스에 맞는 값이 필요하니까요.


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.