글 읽기 - 제대로 짠 것 같은데, 틀렸다고 나오네요.

w3nk18m 7년 전 0

DP 이용해서 풀었는데,

제대로 구현한 것 같은데,

자꾸 틀렸다고 나오네요;;;

구현방식은

1) 각 셀에서 들어 올수 있는 모든 경우를 구함 (주변에 나보다 높은 녀석들 찾음)

2) (0,0)부터 시작해서 각 셀의 완료 상태 체크 (자신에게 들어오는 셀의 상태들이 모두 완료 상태면 나도 완료 상태가 됨)

3) 완료 상태가 되면 자신에게 들어올 수 있는 주변 셀에 저장된 경로를 다 더함

4) (N-1, M-1)이 완료 상태가 될 때까지 무한 루프

어떤 부분이 틀린 것인지 알려주시면 감사하겠습니다.

#include <stdio.h>
#define FOR(i,s,n) for(int i=s; i<n; i++)

int N;
int M;
unsigned long result;
int MAT[500][500];
unsigned long C[500][500][2];

void print(int i)
{
  printf("===== Start [%d] \n", i);
  FOR(i,0,N)
  {
    FOR(j,0,M)
    {
      printf("%d ", C[i][j][0]);
    }
    printf("\n");
  }

  printf("\n");
  FOR(i,0,N)
  {
    FOR(j,0,M)
    {
      printf("%d ", C[i][j][1]);
    }
    printf("\n");
  }
  printf("===== END\n");
  printf("\n");
}

// 내쪽으로 들어 올 수 있는 방향 및 갯수 찾기
void find_direction()
{
  FOR(i,0,N)
  {
    FOR(j,0,M)
    {
      if(MAT[i][j] < MAT[i-1][j] && i != 0)
        C[i][j][1]++;

      if(MAT[i][j] < MAT[i+1][j] && i != N-1)
        C[i][j][1]++;

      if(MAT[i][j] < MAT[i][j-1] && j != 0)
        C[i][j][1]++;

      if(MAT[i][j] < MAT[i][j+1] && j != M-1)
        C[i][j][1]++;
    }
  }
}

// 내 주변(동서남북)에 있는 셀이 계산이 완료 된 것인지 확인
int check_input(int i, int j)
{
  int temp = C[i][j][1];

  if(MAT[i][j] < MAT[i-1][j] && C[i-1][j][1] == 0 && i != 0)
    temp--;

  if(MAT[i][j] < MAT[i+1][j] && C[i+1][j][1] == 0 && i != N-1)
    temp--;

  if(MAT[i][j] < MAT[i][j-1] && C[i][j-1][1] == 0 && j != 0)
    temp--;

  if(MAT[i][j] < MAT[i][j+1] && C[i][j+1][1] == 0 && j != M-1)
    temp--;

//  printf("temp[%d][%d]: %d\n", i,j, temp);

  return temp;
}

// 내 주변(동서남북)에서 들오 올 수 있는 모든 경우 합산
unsigned long sum_route(int i, int j)
{

  unsigned long sum=0;

  if(MAT[i][j] < MAT[i-1][j] && i != 0)
    sum += C[i-1][j][0];

  if(MAT[i][j] < MAT[i+1][j] && i != N-1)
    sum += C[i+1][j][0];

  if(MAT[i][j] < MAT[i][j-1] && j != 0)
    sum += C[i][j-1][0];

  if(MAT[i][j] < MAT[i][j+1] && j != M-1)
    sum += C[i][j+1][0];

  return sum;
}

void dp()
{
  find_direction();
//  print(0);

  C[0][0][0]=1;
  int n=0;
  while(1)
  {
    n++;
    // 최종 목적지 셀이 완료 상태면 종료
    if(C[N-1][M-1][1] == 0)
      return;

    FOR(i,0,N)
    {
      FOR(j,0,M)
      {
        if(C[i][j][1] == 0)
          continue;

        if(check_input(i,j) == 0)
        {
          // 완료 상태로 표시
          C[i][j][1] = 0;
          // 자신에게 들어오는 길 갯수 합산
          C[i][j][0] = sum_route(i,j);

//          print(n);
        }
      }
    }
  }

  return;
}

int main(){
  //freopen("./main.input", "r", stdin);

  scanf("%d %d", &N, &M);
  FOR(i,0,N)
  {
    FOR(j,0,M)
    {
      scanf("%d", &MAT[i][j]);
    }
  }

  dp();

  result = C[N-1][M-1][0];

  printf("%lu\n", result);
  return 0;
}

rhaos 7년 전 1

일단 출발점을 (0,0)이 아닌, (M-1,N-1)에서 시작해서 (0,0)에서 도착하는 것으로 바꿔보는게 좋을듯합니다.

그렇게 하면, 주위 칸들이 계산되었는 지 확인하는과정없이 그대로 재귀호출하면 되겠습니다. (값의 대소값만 비교해서)

w3nk18m 7년 전 0

그렇군요, 근데 (N-1,M-1)에서 진행해도 상향식 방법으로 풀수 있는 건가요? 한번 다시 도전해봐야겠군요.

답변 감사드립니다.

그리고, 제가 짠 알고리즘은 문제가 있는 건지, 궁금하네요, 논리적으로로는솔루션이 나오는 것 같던데, 물론 제 나름대로 테스트도 해봤구요, 뭐가 잘못된 건지 모르겠네요,

타임아웃이 안나는 거 보면, 결과값이 틀린거 같긴한데,

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

문제

문제

출처

ICPC

제대로 짠 것 같은데, 틀렸다고 나오네요.

w3nk18m 7년 전 0

rhaos 7년 전 1

w3nk18m 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말