글 읽기 - [9576] 풀긴 했는데 질문이 있습니다.

eastash 1년 전 0

위에 코드는 틀린코드고 아래코드는 맞은코드인데요

두 코드의 차이점은 단순히 이분매칭을 할때

위: 책 -> 사람 을 찾아가게 구현하였고

아래: 사람 -> 책을 찾아가게 구현하였습니다.

둘이 똑같은 결과를 낼 줄알았는데 위의 방법으로는 어떻게 해도 AC를 받지 못해 아래 방법으로 조금만 틀었더니 AC를 받았습니다.

두 접근 방법에 대해 어떤 차이가 있을까요?

#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits.h>

using namespace std;

int TC;
int B, S;
pair<int, int> SV[1234];
bool vis[1234];
int occBy[1234];

bool dfs(int fromNode) {
  for (int i = 1; i <= S; i++) { // toNode
    if (vis[i] || !(SV[i].first <= fromNode && fromNode <= SV[i].second))
      continue;
    vis[i] = true;
    if (occBy[i] == 0 || dfs(occBy[i])) {
      occBy[i] = fromNode;
      return true;
    }
  }
  return false;
}

int main() {
  cin >> TC;
  int in1, in2;
  for (int T = 1; T <= TC; T++) {
    cin >> B >> S;
    for (int i = 1; i <= S; i++) {
      cin >> in1 >> in2;
      SV[i] = {in1, in2};
    }
    int cnt = 0;
    fill_n(occBy, 1234, 0);
    for (int i = 1; i <= B; i++) {
      fill_n(vis, 1234, false);
      if (dfs(i))
        cnt++;
    }
    cout << cnt << '\n';
  }
}

<----------- 틀린코드 ----------->
#include <algorithm>
#include <cmath>
#include <iostream>
#include <limits.h>

using namespace std;

int TC;
int B, S;
pair<int, int> SV[1234];
bool vis[1234];
int occBy[1234];

bool dfs(int fromNode) {
  for (int i = SV[fromNode].first; i <= SV[fromNode].second; i++) { // toNode
    if (vis[i])
      continue;
    vis[i] = true;
    if (occBy[i] == 0 || dfs(occBy[i])) {
      occBy[i] = fromNode;
      return true;
    }
  }
  return false;
}

int main() {
  cin >> TC;
  int in1, in2;
  for (int T = 1; T <= TC; T++) {
    cin >> B >> S;
    for (int i = 1; i <= S; i++) {
      cin >> in1 >> in2;
      SV[i] = {in1, in2};
    }
    int cnt = 0;
    fill_n(occBy, 1234, 0);
    for (int i = 1; i <= S; i++) {
      fill_n(vis, 1234, false);
      if (dfs(i))
        cnt++;
    }
    cout << cnt << '\n';
  }
}

<----------맞은 코드----------->

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

문제

문제

출처

ICPC

[9576] 풀긴 했는데 질문이 있습니다.

eastash 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말