글 읽기 - [1699]이코드가 틀린이유가뭘까요??? 결과는 잘 나오는것 같은데요..

kioio5 6년 전 1

이 코드가 틀린이유가뭘까요??? 결과는 잘 나오는것 같은데요..

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int dp[100001];
int n;

void process()
{
    long i,j;
    long k;

    for(i=1; i<=n; i++)
    {
        k = sqrt(i);
        dp[i] = dp[k*k]+dp[i-k*k];
        if(k*k==i)
            dp[i]=1;

    }

   printf("%d\n",dp[n]);

}

int main()
{

    scanf("%d",&n);
    process();
    return 0;
}

chogahui05 6년 전 3

dp[i] = dp[k*k] + dp[i-k*k]라..

k야 sqrt해서 나오는 것일 테고.. i 이하인 가장 큰 제곱수를 택한다는 그리디 전략이 아닌가요?

사실 반례가 있죠.

답 : 16 + 16

님이 선택하는 전략에 따르면

32 = 25 + 7

= 25 + 4 + 3

= 25 + 4 + 1 + 1 + 1

이렇게 됩니다.

chogahui05 6년 전 1

그리고.. sqrt 함수를 호출할 필요가 있을지는 모르겠습니다만.. 비용이 그렇게 많이 드는 것도 아니고..

i*i <= j 조건을 (돌 때마다) 검사할 바에야. sqrt를 한 번 정도 호출해 줘서 i <= k 조건으로 단순화 시키는 것도

나쁘지 않은 생각인 거 같네요.

kioio5 6년 전 0

와우..... 반례 정말 감사합니다 !!

고맙습니다!!!!!

!_!

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

문제

문제

출처

ICPC

[1699]이코드가 틀린이유가뭘까요??? 결과는 잘 나오는것 같은데요..

kioio5 6년 전 1

chogahui05 6년 전 3

chogahui05 6년 전 1

kioio5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말