글 읽기 - C++ 시간 초과 이유 알려주세요...

kimsan 1년 전 0

c++ 시간 초과 나는이유 알려주세요 ㅠㅠㅠ

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <numeric>
#include <queue>
#include <stack>
#include <algorithm>
#include <map>
using namespace std;

int n, m;
vector<pair<int, int>> house;
vector<pair<pair<int, int>, bool>> chicken;
vector<pair<int, int>> select_chicken;
int answer = 987654321;

void func(int x, int t) {
    if (x == m) {
        int sum = 0;
        for (int i = 0; i < house.size(); i++) {
            int my_min = 987654321;
            for (int j = 0; j < select_chicken.size(); j++) {
                my_min = min(my_min, abs(select_chicken[j].first - house[i].first) + abs(select_chicken[j].second - house[i].second));
            }
            sum += my_min;
        }
        answer = min(answer, sum);
        return;
    }
    for (int i = t; i < chicken.size(); i++) {
        if (!chicken[i].second) {
            chicken[i].second = true;
            select_chicken.push_back({ chicken[i].first.first, chicken[i].first.second });
            func(x + 1, t + 1);
            chicken[i].second = false;
            select_chicken.pop_back();
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int tmp;
            cin >> tmp;
            if (tmp == 1) {
                house.push_back({ i, j });
            }
            if (tmp == 2) {
                chicken.push_back({ { i, j }, false });
            }
        }
    }
    func(0, 0);
    cout << answer;
    return 0;
}

yhj1937 1년 전 4

35번째 줄에 t + 1이 문제입니다. i 번째 치킨집을 선택했다면 이후에는 i + 1번째부터 고르면 되는데 t + 1 부터 고르면 앞에 것으로 돌아오는 상황이 생길테니 중복되는 경우를 검사하게 됩니다.

npole0103 1년 전 2

@yhj1937
저도 i + 1 해야할 것을 t + 1해서 똑같은 문제로 시간초과 떴는데 덕분에 해결했습니다. 감사합니다 :)

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

문제

문제

출처

ICPC

C++ 시간 초과 이유 알려주세요...

kimsan 1년 전 0

yhj1937 1년 전 4

npole0103 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말