글 읽기 - 처음부터 틀리는데 도와주세요!

bub3690 5년 전 0

반례가 있나요? ㅠㅠ 처음부터 바로 틀리는데,,

일단 제가 사례를 넣었을때는 전부 맞았습니다.

이분 트리를 재귀함수로 전체 탐색하듯 코드를 짰습니다.

#include<iostream>
#include<algorithm>
using namespace std;
int na[9];
int dp[9];
const int max_height = 100;
bool flag=false;

void nansum(int n,int sum_height,bool take,int count){
	if (n > 8 || sum_height>max_height) {
		return;
	}
	if(count == 7 && sum_height == max_height) {
		flag = true;
	}
	if (flag) {
		if (take)dp[n] = na[n];
		return;
	}
	if (!flag)nansum(n+1, sum_height, false, count);
	if(!flag) nansum(n+1, sum_height+na[n+1], true, count+1);
	
	if (flag) {
		if (take)dp[n] = na[n];
		return;
	}
}
int main() {
	ios::sync_with_stdio(false);
	for (int i = 0; i < 9; i++) {
		cin >> na[i];
		dp[i] = -1;
	}

	nansum(0, 0,false,0);
	nansum(0, na[0],true,1);

	sort(dp,dp+9);
	for (int i = 0; i < 9; i++) {
		if (dp[i] != -1) {
			cout << dp[i] << "\n";
		}
	}
}

zxcvber 5년 전 1

다음과 같은 반례를 찾았습니다

입력

10 11 12 13 14 15 1 25 20

출력

1 10 12 13 14 15 20 25

(합 110)

정답(으로 가능한 것)

10 11 12 13 14 15 25

1 12 13 14 15 20 25

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

문제

문제

출처

ICPC

처음부터 틀리는데 도와주세요!

bub3690 5년 전 0

zxcvber 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말