글 읽기 - [1699] 하나만 바꿨을 뿐인데 정답에서 틀렸다고 나옵니다. 이유가 뭘까요?

ddi04078 4년 전 0

아래 코드(틀린 코드)를 보시면

len에 넣을 때 말고 dp에 값을 할당할때 +1을 했더니 틀렸다고 뜹니다.

하지만 len에 넣을 때 +1을 하면 정답이라고 뜹니다.

코드로 설명하자면

33번 줄에서

len.push_back(dp[i-sqNums[j]]);

를

len.push_back(dp[i-sqNums[j]]+1);

로 고치고

37번 줄에서

dp[i] = *min_element(len.begin(), len.end())+1;

를

dp[i] = *min_element(len.begin(), len.end());

로 고치면 정답이 뜹니다...

아래의 코드에서 뭐가 잘못됐을까요?

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
	int n;
	cin>>n;

	//dp[i] : i를 제곱 수로 나타냈을 때 항이 최소인 경우의 항 수 
	int dp[100001]; //자연수 100000이므로 배열 크기는 100001

	//제곱수를 그때그때 검사하지말고, 미리 배열로 만들어 놓는다.
	vector<int> sqNums;
	int sq;
	for(int i=1; i<=100000; i++){
		sq = sqrt(i);//제곱수를 정수형으로 만드는
		if( sqrt(i)==sq ){ //정수형과 sqrt값이 같다면 sqrt가 정수라는 뜻이므로 제곱수다.
			sqNums.push_back(i);
		}
	}

	for(int i=1; i<=n; i++){ 
		vector<int> len; //가능한 항수(항길이) 경우를 모두 넣고  최소값을 빼내면 그 값이 dp[i]

		//sqNums 배열 안의 제곱수들로 진행
		for(int j=0; j<sqNums.size(); j++){
			//dp[i]값 찾으려는 i보다 제곱수가 작아야하므로 (같으면 검사해도 되므로 등호 뺀다.)
			if(sqNums[j] > i) break;
			//그게 아니면 len에 넣음 
			len.push_back(dp[i-sqNums[j]]);
		}
		
		// 가능한 모든 경우 중 최소값이 dp[i]
		dp[i] = *min_element(len.begin(), len.end())+1; 
	}

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

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

문제

문제

출처

ICPC

[1699] 하나만 바꿨을 뿐인데 정답에서 틀렸다고 나옵니다. 이유가 뭘까요?

ddi04078 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말