글 읽기 - 조합으로 풀었을때의 코드 차이가 궁금합니다!

dhwhc0711 3년 전 0

2번 코드로 시도를 하다 1번 코드로 수정후에 정답입니다를 받았습니다.

2번 코드의 경우

check 배열을 사용해 백트래킹을 해준 코드입니다. 이 경우에 여러가지 조합의 경우의 수가 나오는 것이 아닌 맨 마지막 경우의 수 1개만 출력되게 됩니다..

어떤 차이가 있는지 알 수 있을까요?

시간 내주셔서 감사합니다!

// 1번 정답 코드
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int k;

void recur(int start, int depth, vector<int> &num, vector<int> answer, bool check[])
{
    if (depth == 6)
    {
        for (int i = 0; i < 6; i++)
        {
            cout << answer[i] << " ";
        }
        cout << "\n";
        return;
    }

    else
    {
        for (int i = start; i < k; i++)
        {
            answer[depth] = num[i];
            recur(i + 1, depth + 1, num, answer, check);
        }
    }
    return;
}

int main()
{
    while (true)
    {
        cin >> k;

        if (k == 0)
            break;

        else
        {
            vector<int> num(k, 0);
            vector<int> answer(k, 0);
            bool check[k];
            for (int i = 0; i < k; i++)
            {
                cin >> num[i];
            }
            recur(0, 0, num, answer, check);
            cout << "\n";
        }
    }
}

// 2번 오답 코드

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

using namespace std;
int k;

void recur(int start, int depth, vector<int> &num, vector<int> answer, bool check[])
{
    if (depth == 6)
    {
        for (int i = 0; i < 6; i++)
        {
            cout << answer[i] << " ";
        }
        cout << "\n";
        return;
    }

    else
    {
        for (int i = start; i < k; i++)
        {
            // 이 부분에서의 차이점이 궁금합니다.
            if (!check[i])
            {
                check[i] = true;
                answer[depth] = num[i];
                recur(i + 1, depth + 1, num, answer, check);
                check[i] = false;
            }
            // 차이점 끝
        }
    }
    return;
}

int main()
{
    while (true)
    {
        cin >> k;

        if (k == 0)
            break;
        else
        {
            vector<int> num(k, 0);
            vector<int> answer(k, 0);
            bool check[k];
            for (int i = 0; i < k; i++)
            {
                cin >> num[i];
            }
            recur(0, 0, num, answer, check);
            cout << "\n";
        }
    }
}

djm03178 3년 전 1

check 배열이 초기화되지 않아 처음에 무슨 값이 들어있을지 알 수 없습니다.

dhwhc0711 3년 전 0

@djm03178

계속해서 실수하는 부분이네요 ㅠㅠ 귀중한 시간 내주셔서 감사합니다!!

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

문제

문제

출처

ICPC

조합으로 풀었을때의 코드 차이가 궁금합니다!

dhwhc0711 3년 전 0

djm03178 3년 전 1

dhwhc0711 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말