글 읽기 - 1699번 제곱수의 합 85%에서 실패했습니다.

wlckd90 5년 전 0

0,1,2에 초기값을 넣어 줬고요

완전 제곱수 들에 1로 초기화 해줬습니다.

나머지 dp값들은 예를 들어, j번째는 j와 가장 가까운 제곱수를 고르고 1과 dp[j-가장가까운 제곱수]를 dp[j]로 계산했습니다.

이때 가장 가까운 제곱수가 항상 최적은 아니므로 반복문을 통해 j와 가장 가까운 수 부터 1까지 제곱수들을 계산했습니다.

예를 들어 dp[32]를 계산할때는

32와 가장 가까운 제곱수는 25니까

1+ dp[32-25]

1+ dp[32-16]

1+ dp[32-9]

1+ dp[32-4]

1+dp[32-1]

을 계산해서 최솟값을 구했습니다.

다른 질문들에 있는 반례들 넣어봐도 잘 되는데 왜 틀렸습니다 뜨는지 모르겠어요!

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int n, dp[100001], min, sqr;
	cin >> n;
	
	for (int i = 1; i < 317; i++) {
		dp[i*i] = 1;
	}
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;

	for (int j = 3; j < 100001; j++) {
		if (dp[j] == 1)
			continue;
		sqr = int(sqrt(j));
		min = 10000;
		for (int k = sqr; k >= 1; k--) {
			int temp = 1 + dp[j - (k*k)];
			if (min > temp) {
				min = temp;
				dp[j] = min;
			}
		}
	}

	cout << dp[n] <<'\n';
	return 0;
}

djm03178 5년 전 2

17, 18번째 줄을 지우면 맞습니다.

왜냐하면, dp 배열이 초기화되지 않고 일부 원소에만 값을 대입했기 때문에 나머지 원소들은 무슨 값을 가지고 있을지 모르는데, 만일 '우연히' 1이 들어있었을 경우 그냥 넘어가기 때문입니다.

wlckd90 5년 전 0

djm03178님 답변 감사합니다.

실제로 지우고 실행해보니 통과했습니다.

그리고

int dp[100001] = { 0, };을 추가해도 맞았습니다.

한가지 궁금한게 '우연히' 1이 들어있을 경우가 있으니까 초기화를 해야겠네요... 감사합니다

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

문제

문제

출처

ICPC

1699번 제곱수의 합 85%에서 실패했습니다.

wlckd90 5년 전 0

djm03178 5년 전 2

wlckd90 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말