글 읽기 - 다이내믹프로그래밍이 익숙치않는 1인입니다. 시간초과문제

gaelim 5년 전 2

bottom-up과 up-bottom이 같다고 생각하기에 ,,,

한번 메모이제이션을 써보았습니다.

제가 제대로 메모이 제이션을 썼는지 의문입니다.... 코드는 짧아서 읽으실때 괜찮겠습니다만...

뭔가 작은 테스트케이스는 잘 맞는거같습니다.

문제는 시간초과입니다. 이런 문제는 구현을 3중 for문으로 해야할까요?

아니면 이정도도 그럭저럭 괜찮은 다이내믹프로그래밍을 했다고할 수있을까요?

아니면 완전 틀렸나요? 시간초과가 난거보니까 제가 메모이제이션도 제대로 안한거같기도하고 ㅠ.ㅠ

#include <stdio.h>

typedef struct array{ long long r, c; }array;
array a[501];
long long d[501][501];

int min(int n, int m) { if (n<m) return n; return m;}

long long dfs(int l, int r){
  if (l==r-1) return d[l][r]=a[l].r*a[l].c*a[r].c;
  if (l==r) return d[l][r]=0;
  if (d[l][r]) return d[l][r];
  d[l][r]=1<<50;
  for (int i=l; i<r; i++){
    d[l][r]=min(dfs(l,i)+dfs(i+1,r)+a[l].r*a[i].c*a[r].c,d[l][r]);
  }
  return d[l][r];
}

int main(){

  int n;
  scanf("%d", &n);
  for (int i=1; i<=n; i++) scanf("%lld %lld", &a[i].r, &a[i].c);

  dfs(1, n);
  printf("%lld\n", d[1][n]);
}

gaelim 5년 전 0

g허... dfs 함수 안에 쓸모없는 명제가 있는가봐요.

몇개 지우니까 통과되네요... 하 어렵다 ...... 특히 (l==r) return d[l][r]=0 이나 (l==r) return 0 과 연산속도가 다른가요... 허허 ... ㅠ.ㅠ...?

gaelim 5년 전 0

@doju long long data type 인 경우 LL 자를 붙여줘야 비트쉬프트가 사용가능한것을 뜻하신거죠??

1 << 50 은 int type이고, 1LL << 50 은 long long type입니다. 그리고 left shift operator는 결과값이 자료형이 표현 가능한 범위를 넘어갈 때 undefined behavior를 일으킵니다. 즉 환경마다, 계산할 때마다 값이 달라질 수도 있고 프로그램이 꺼질 수도 있고 컴퓨터가 로봇 혁명을 일으킬 수도 있습니다.
https://ideone.com/SwCKzR

로컬에서는 작은 테스트 케이스가 잘 나온다고 하셨으니 적당히 큰 어떤 값이 나온 모양이지만, BOJ에서는 운 나쁘게 0이 나오는 바람에 시간 초과가 발생한 것입니다.

gaelim 5년 전 0

@doju 와우 상세하게 설명해주셔서 감사합니다. 그것이 문제 였었네요 감사합니다 와우

gaelim 5년 전 0

혼자 생각해서 결론내렸다면 완전 이상한 개념이 생길뻔했군요.... 감사합니다

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

문제

문제

출처

ICPC

다이내믹프로그래밍이 익숙치않는 1인입니다. 시간초과문제

gaelim 5년 전 2

gaelim 5년 전 0

doju 5년 전 1

gaelim 5년 전 0

doju 5년 전 2

gaelim 5년 전 0

gaelim 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말