글 읽기 - 시간을 어떻게 줄일 수 있을까요.

paranocean 6년 전 0

Bottom-UP으로 한번 풀고, 그 다음에 top-down 재귀로 풀어보려 하는데 시간이 너무 걸립니다. 그리디로 미리 근사해를 메모에 적어놓고 그 다음에 TopDown()함수를 써보는 것도 해봤는데 그래도 느려요. 어떻게 개선할 수 있을까요. 조언을 구합니다.

#include <stdio.h>

int Triangle[500][500];
int max=0;
int memo[500][500];
void TopDOWN(int curr_sum, int W, int H)
{
  curr_sum+=Triangle[H][W];
  if (memo[H][W]>curr_sum)
    return;
  if (!memo[H][W])
    memo[H][W]=curr_sum;
  if (H==0)
  {
    if (curr_sum>max)
      max=curr_sum;
    return; //맨 위층이다. 백트랙.
  }
  if (W-1>=0)
    TopDOWN(curr_sum, W-1, H-1);
  if (W<=H)
    TopDOWN(curr_sum, W, H-1);
}
void greedy(int curr_sum, int W, int H)
{
  curr_sum+=Triangle[H][W];
  if (memo[H][W]>curr_sum)
    return;
  if (!memo[H][W])
    memo[H][W]=curr_sum;
  if (H==0)
  {
    if (curr_sum>max)
      max=curr_sum;
    return; //맨 위층이다. 백트랙.
  }
  greedy(curr_sum, Triangle[H-1][W-1]>Triangle[H-1][W]? W-1 : W, H-1);
}
int memo[500][500];
int main(void)
{
  int n;
  scanf("%d",&n);
  for (int H=0; H<n; H++)
    for (int W=0; W<=H; W++)
      scanf("%d",&Triangle[H][W]);
  for (int W=0; W<n; W++)
    greedy(0, W, n-1);
  for (int W=0; W<n; W++)
  {
    TopDOWN(0, W, n-1);
    printf("%d th Top-Down complete\n",W);
  }

  printf("TopDOWN=%d", max);

  return 0;
}

chogahui05 6년 전 0

어떻게 개선하느냐..

a라는 위치에 온 경우 이전에 있었던 위치는 후보해를 생각해 보시면 쉽습니다..

무슨 소리냐면 aaa라는 위치에 있을 때

bbb에 있거나 ccc에 있을 수가 있을 겁니다.

그런데 bbb에 왔을 때는 kkk에 있거나 ggg에 있거나.. 이런 상태가 나타난단 말이죠..

즉, dp[x][y]를 위치 x,y에 왔을 때 최대치. 라고 생각하시고 memoi 하시면 시간 줄이실 수 있어요.

chogahui05 6년 전 0

bottom up? 하실 때에는 dp배열 잘 하셨네요..

재귀식으로 top down 하는 것도 다르지 않을 거 같아요..

paranocean 6년 전 0

풀었습니다. 감사합니다.

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

문제

문제

출처

ICPC

시간을 어떻게 줄일 수 있을까요.

paranocean 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 0

paranocean 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말