글 읽기 - 왜 틀린지 모르겠어요..

hanmar88 7년 전 0

정답인 코드와 전체 1~100000까지 d 배열을 비교했을 때, 모두 동일한데,

왜 틀림으로 나오는지 모르겠어요..

아시는 분은 알려주세요~

#include <cstdio>
int d[100001];
int ze[400];
int main(){
	int n;
	scanf("%d", &n);
	for(int i=1;i*i<=n;i++){
		ze[i]=i*i;
		d[i*i]=1;
	}
	for(int i=2;i<=n;i++){
		if(d[i]!=1){
			d[i]=d[i-ze[1]]+1;
			for(int j=2;i>ze[j];j++){
				if(d[i]>d[i-ze[j]]+1) {
					d[i]=d[i-ze[j]]+1;
				}
			}
		}
	}
	printf("%d\n", d[n]);
	return 0;
}

plzrun 7년 전 0

그러게요.. 1부터 10만까지 전부다 넣고 돌린다음에 맞은 코드 출력이랑 비교했는데

틀린게 하나도 없는뎅...

이거 뭔가 문제가 이상한데요?

안에 테케 이상한게 들어가있는거 같아요

plzrun 7년 전 0

https://www.acmicpc.net/board/view/8705

plzrun 7년 전 0

longlong으로 바꾸니까 답이 맞았다고 뜨네요.

#include <cstdio>
int d[100001];
long long ze[400];
int main(){
    int n;
    scanf("%d", &n);
    for(long long i=1LL;i*i<=n;i++){
        ze[i]=i*i;
        d[i*i]=1;
    }
    for(int i=2;i<=n;i++){
        if(d[i]!=1){
            d[i]=d[i-ze[1]]+1;
            for(int j=2;i>ze[j];j++){
                if(d[i]>d[i-ze[j]]+1) {
                    d[i]=d[i-ze[j]]+1;
                }
            }
        }
    }
    printf("%d\n", d[n]);
    return 0;
}

plzrun 7년 전 0

ze값 400개 다 들여다 봤는데

long long 넘어갈 값이 전혀 없는뎅... 뭘까요 ?;; ㄷㄷ

wowoto9772 7년 전 0

이건 제가 맞은 소스코드에요.

long long 사용하지 않고 해결했는데,

i*i를 계산하는 과정에서 int를 초과한것 아닐까요?

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int dp[100003];
 
int main() {
 
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)dp[i] = i;
 
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j*j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j*j] + 1);
        }
    }
 
    printf("%d\n", dp[n]);
 
}

yukariko 7년 전 5

제가 생각하는 원인은 데이터가 아니라 바로 다음의 코드라고 생각합니다.

for(int j=2;i>ze[j];j++){

ze배열은 제곱수를 저장하는 배열로, 위 코드는 i보다 작은 제곱수에 대해 반복하게 되어있습니다.

하지만, i보다 큰 제곱수가 없을경우 오버플로우가 발생하게 됩니다.

N 이 10인 경우를 예로들어봅시다.

i는 N까지 반복하기때문에 i = 10이 될 수 있죠.

이때 ze배열에는 1, 4, 9의 숫자가 들어있습니다.

이때 4, 9를 방문하고 반복문이 끝나야 의도한 코드가 되겠지만, 위 코드에선 그렇지않고 더 큰수가 나올때까지 계속 탐색하게됩니다.

ze배열은 전역이므로 0으로 초기화 되어있을태니 1 4 9 0 0 0 0 0... 을 계속 반복하다가 더 큰수가 나올때 종료되겠죠.

이 다음은 오버플로우이기때문에 어떤 값이 나오게 될지 모르고 따라서 채점환경에따라 다른 답을 도출할 수 있습니다.

plzrun 7년 전 0

아 그렇군요 @yukariko님이 말씀해주신 것 때문에 그렇겠네요 ㅎㅎ

@wowoto9772님이 말씀해 주신 부분은 i*i가 n이하고 n이 10만이니까 그것때문은 아닌거 같아요.

그럼 올려두었던 의견글은 삭제를 하도록 하겠습니다. :)

hanmar88 7년 전 0

아 그렇네요..

뭔가 깔끔하지 못했던 코드 같아요..

알려주셔서 감사합니다.

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

문제

문제

출처

ICPC

왜 틀린지 모르겠어요..

hanmar88 7년 전 0

plzrun 7년 전 0

plzrun 7년 전 0

plzrun 7년 전 0

plzrun 7년 전 0

wowoto9772 7년 전 0

yukariko 7년 전 5

plzrun 7년 전 0

hanmar88 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말