글 읽기 - 코드 질문입니다. 틀린 이유를 모르겠어요..

qptnnm 7년 전 0

결과가 다 맞는거 같은데.. 어디가 틀렸는지 도와주세요 ㅠㅠ

​

#include <stdio.h>
#include <stdlib.h>

#define max(a,b) (((a)>(b))?(a):(b))
int dp[100001];

int main()
{
    int N;
    scanf("%d", &N);

    int i;
    long long j = 1;
    for (i = 1; i <= N; i++)
    {
        if (i > j*j) {
            j++;
        }

        if (i == j*j) {
            dp[i] = 1;
        }
        else {
            dp[i] = dp[i-(j-1)*(j-1)] + 1;
        }
    }
    printf("%d\n", dp[N]);
    return 0;
}

zlzmsrhak 7년 전 0

12 = 3²+ 1²+ 1²+ 1²

최적은 ,12 = 2²+2²+2²

그리디로 가장 큰 것부터 골라 나가면 반례가 생깁니다.

qptnnm 7년 전 0

감사합니다 ! 비슷한 질문 글이 있었는데... 확인하지 못하고 중복해서 올렸네요...

답변 감사드립니다 !

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

문제

문제

출처

ICPC

코드 질문입니다. 틀린 이유를 모르겠어요..

qptnnm 7년 전 0

zlzmsrhak 7년 전 0

qptnnm 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말