gaelim   3년 전

목표값과의 차의 절대값을 구하려고 하니까 충분히 큰 숫자로 주려고 long long 타입으로 했구요.
초기값을 이렇게 1<<22 로 주고 돌려봤는데 제가
생각하는 예외
5 20
100 100 100 100 100
하면 답이 300 나와야하는거 맞는거같구요..

5 300000
100 200 300 400000 50000
400300 에도 이렇게 나오구요..

그런데 반례가 뭔지 모르겠어요... ㅠ.ㅠ 고수님들의 도움이 필요합니다. 


#include <stdio.h>
long long a[101], d[101][4];
int n, obj;
int min(long long a, long long b){
  if ((a-obj)*(a-obj) > (b-obj)*(b-obj)) return b; return a;
}

int main(){

  scanf("%d %d", &n, &obj);
  for (int i=0; i<n; i++) scanf("%lld", &a[i]);

  d[0][2]=1<<22; d[0][3]=1<<22; d[0][1]=a[0];
  d[1][1]=a[1]; d[1][2]=a[0]+a[1]; d[1][3]=1<<22;

  for (int i=2; i<n; i++ ){
    d[i][1]=a[i]; d[i][2]=1<<22; d[i][3]=1<<22;
    for (int j=0; j<i; j++){
      d[i][2]=min(d[j][1]+a[i],d[i][2]);
      d[i][3]=min(d[j][2]+a[i],d[i][3]);
    }
  }

  long long ans=1<<20;
  for (int i=0; i<n; i++) ans=min(ans,d[i][3]);
  printf("%lld\n", ans);
}

sgchoi5   3년 전

COCI 문제는 대회에서 사용했던 TC 가 공개되어 있습니다.. 그걸로 해보세요..

http://gooddaytocode.blogspot....

gaelim   3년 전

@sgchoi5 감사합니다~~~반례 찾았습니다~~ ㅠ.ㅠ 확실히 어떤 지점에서의... 그런지는 아직은 모르겠지만 확실히 다르네요!! 감사합니다

nhouyng   3년 전

5 20
100 100 100 100 100 하면 300이 나와야한다는 예외는 틀린것같습니다.

제가 방금 제출해서 맞았는데 위 같은 경우는 0이 나와야합니다. 기준m보다 적은수에서 최대값을 찾아야하기 때문입니다.

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