글 읽기 - 질문에 있는 test, 문제 test 다 맞는데 왜 틀릴까요?

ohbg123 6년 전 0

질문에 있는 test, 문제 test 다 맞는데 왜 틀릴까요?

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1001;
int dp[MAX];
int arr[MAX];
int N, result = -10;

int maxPrice(int num){
	if (num == 0){ return 0; }
	if (dp[num] != -1){ return dp[num]; }
	
	for (int i = 1; i <= N; i++){
		if ((num % i) == 0)
			result = max(maxPrice(num - i) + arr[i], result);
	}
	dp[num] = result;

	return dp[num];
}

int main(void){
	cin >> N;
	
	fill(dp, dp + MAX, -1);
	for (int i = 1; i <= N; i++){
		int temp;
		cin >> temp; if (temp > 10000){ return 0; }
		arr[i] = temp;
	}

	cout << maxPrice(N) << endl;
}

yclock 6년 전 1

16번째 줄의 if문이 이해가 되지 않네요..

yclock 6년 전 1

15번째 줄에서 for문을 1부터 N까지 돌고 있습니다.

yclock 6년 전 0

30번째 줄에서 입력이 올바른지 검사하지 않으셔도 됩니다.

ohbg123 6년 전 0

1 5 6 7

N이 4라고 가정하면 처음에 num이 4가 되고 i가 1일때 num이 1로 계속 나누어 떨어지기 때문에 0까지 찍고 return 0 된 후 0+arr[1]로 result가 1되죠

이때 num이 1이기 때문에 for문이 끝나고 return 1 됩니다. 그 다음 num이 2가 되고 i가 1일때 1 + arr[1]은 2이고 i가 2일때 0 + arr[2] 즉 5가되고 다시 for문이 끝납니다. if문으로 걸러지는 구조입니다.

ohbg123 6년 전 1

헐... if문 지우고 범위 바꾸니까 돌아갑니다!

yclock 6년 전 2

16번째 줄의 if문은 올바르지 않습니다.

N = 5이고, 해집합이 {2, 3}으로 모두 N의 약수가 아닐 경우, 본 소스코드는 올바르지 못한 결과를 출력합니다.

다음은 반례 데이터입니다.

Input:
5
1 1000 2000 1 1

Correct Output:
3000

Your Output:
2002

ohbg123 6년 전 1

친절한 답변 감사합니다!!!^^

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

문제

문제

출처

ICPC

질문에 있는 test, 문제 test 다 맞는데 왜 틀릴까요?

ohbg123 6년 전 0

yclock 6년 전 1

yclock 6년 전 1

yclock 6년 전 0

ohbg123 6년 전 0

ohbg123 6년 전 1

yclock 6년 전 2

ohbg123 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말