목표값과의 차의 절대값을 구하려고 하니까 충분히 큰 숫자로 주려고 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; }
gaelim 6년 전
목표값과의 차의 절대값을 구하려고 하니까 충분히 큰 숫자로 주려고 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);
}