글 읽기 - 완전탐색 알고리즘이 틀린걸까요??

moonsoo5522 8년 전 0

여태 반복DP만 풀고 재귀를 등한시한 탓인지 재귀짜는게 어렵더라구요

이문제도 다른 쉬운 풀이법이 있지만 일단 재귀 연습삼아 재귀버전으로 풀고있는데...

자꾸 틀렸다 나오네요 8ㅅ8

난쟁이가 7명이 됐을때 합산 키가 100일경우 출력하고 리턴하는 방식입니다.

키가 100인 경우는 단 한번이라길래 따로 예외처리를 안했는데요

어디가 잘못된걸까요 ㅎㅎ..

#include <stdio.h>
#include <stdlib.h>

int arr[10];
int stack[10];

int cmp(const void *arg1, const void *arg2)
{
    return *(int *)arg1 > *(int *)arg2 ? 1 : *(int *)arg1 < *(int *)arg2 ? -1 : 0;
}

// idx = 현재 인덱스번호, n = 선택된 난쟁이 갯수, sum = n-1 마리 난쟁이의 키 합산
void rec(int idx, int n, int sum)
{
    stack[n]=arr[idx]; // 트래킹 정보 저장
    if(n == 7)
    {
        if(arr[idx]+sum == 100)
        {
            qsort(stack+1, 7, sizeof(int), cmp);
            for(int i=1; i<=7; i++)
                printf("%d\n", stack[i]);
        }
        return;
    }
    
    for(int i=idx; i<8; i++)
        rec(i+1, n+1, arr[idx]+sum);
}
int main()
{
    for(int i=0; i<9; i++)
        scanf("%d", &arr[i]);
    
    rec(0, 1, 0);
}

booboo 8년 전 1

35번째 줄의 rec(0, 1, 0); 는 0번 난쟁이는 무조건 선택하는 것 같은데, 이렇게 해서 답을 찾지 못하면 rec(0, 0, 0);을 다시 해봐야 할 것 같습니다.

그리고 28번째 줄의 rec(i+1, n+1, arr[idx]+sum); 부분도 같은 맥락에서 고쳐주셔야 할 것으로 보입니다.

moonsoo5522 8년 전 0

아...그러네요.. 그부분을..

다시 해보겠습니다 ㅎㅎ

taewony 8년 전 0

아래처럼 고쳐 보았는데, 틀리다고 나오네요. 주어진 예제 data는 맞게 나오는데, 뭐가 문제일까요?

#include <cstdio>
#include <cstdlib>

int arr[10];
int stack[10];

int cmp(const void *arg1, const void *arg2) {
	return *(int *)arg1 > *(int *)arg2 ? 1 : *(int *)arg1 < *(int *)arg2 ? -1 : 0;
}

void print() {
	qsort(stack, 7, sizeof(int), cmp);
	for (int i = 0; i < 7; i++)
		printf("%d\n", stack[i]);
}
// idx = 현재 인덱스번호, n = 선택된 난쟁이 갯수, sum = n-1 마리 난쟁이의 키 합산
int rec(int idx, int n, int sum) {
	stack[n] = arr[idx]; // 트래킹 정보 저장
	if (n == 6) {
		if (sum + arr[idx] == 100)
			return 1;
		return 0;
	}
	if (idx == 8)
		return 0;
	
	if (rec(idx + 1, n + 1, sum + arr[idx])) return 1;
	return rec(idx + 1, n, sum);
}
int main() {
	for (int i = 0; i<9; i++)
		scanf("%d", &arr[i]);

	stack[0] = arr[0];
	if (rec(1, 1, arr[0])) print();
	if (rec(1, 0, 0)) print();
	return 0;
}

moonsoo5522 8년 전 0

저도 찾기가 힘드네요..ㅋㅋㅋ

따로 질문글을 따로 올리시는게 좋을거 같아요..

일단 제 소스에서 메인함수 가장 밑에 rec(1, 1, 0); rec(2, 1, 0); 두줄 추가하면 정답 뜰거에요.

제출하고나서 오픈소스 보시는것도 괜찮을거 같네요.

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

문제

문제

출처

ICPC

완전탐색 알고리즘이 틀린걸까요??

moonsoo5522 8년 전 0

booboo 8년 전 1

moonsoo5522 8년 전 0

taewony 8년 전 0

moonsoo5522 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말