글 읽기 - 시간 초과가 뜹니다. 어느 부분을 개선해야 할까요?

deepred 3년 전 0

문제 3줄요약

1. 반 학생의 수, 친구관계 수를 입력받고 첫 줄에 입력받고 그 다음줄부터 친구관계들을 입력받습니다. ("1 2"로 입력이 들어왔다면 1과 2는 서로 친구입니다)

2. 친구끼리만 짝을 지을 수 있습니다. 짝끼리 무대에 올라가 춤을 춥니다. 짝이 없더라도 최대 1명은 혼자 무대에 올라가 나홀로댄스를 출 수 있습니다.

3. 이때 무대에 올라갈 수 있는 최대 인원을 구하는 문제입니다

========================================================================

정말 정직하게 브루트포스+재귀로 풀었는데 시간초과가 뜨네요

어느 부분을 개선해야 할지 방향이 잘 잡히지 않아 질문 드립니다.

키워드만 툭 던져주셔도 좋으니 조언 부탁드리겠습니다!

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Objects;
import java.util.StringTokenizer;
import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;

class Main {
  public static void main(String[] args) throws Exception {
    // Input은 제가 만든 클래스인데 Scanner로 보시면 됩니다
    final int MATES_AMOUNT = Input.nextInt();
    final int RELATIONS = Input.nextInt();

    Mates mates = new Mates(MATES_AMOUNT);
    
    List<Pair> pairs = new ArrayList<>();
    for (int i = 0; i < RELATIONS; i++) {
      int friendA = Input.nextInt();
      int friendB = Input.nextInt();
      pairs.add(new Pair(friendA, friendB));
    }

    int maxAvailable = calcMaxAvailableToBeStage(mates, pairs);
    System.out.print(maxAvailable);
  }

  static int calcMaxAvailableToBeStage(Mates mates, List<Pair> pairs) {
    if (pairs.isEmpty() || mates.getAmount() <= 1) {
      return mates.isAnyoneLeft() ? 1 : 0;
    }
    
    int maxAvailable = 0;
    for (int i = 0; i < pairs.size(); i++) {
      Pair pair = pairs.get(i);
      if (!mates.isAvailablePair(pair)) continue;
      int available = 2;
      
      pairs.remove(pair);
      mates.exludePair(pair);
      available += calcMaxAvailableToBeStage(mates, pairs);
      mates.includePair(pair);
      pairs.add(i, pair);

      maxAvailable = Math.max(available, maxAvailable);
    }

    return maxAvailable;
  }
}

class Mates {
  private boolean[] mates;

  public Mates(int matesAmount) {
    mates = new boolean[matesAmount];
    Arrays.fill(mates, true);
  }

  public boolean isAvailablePair(Pair pair) {
    return mates[pair.getFriendA() - 1]
      && mates[pair.getFriendB() - 1];
  }

  public void exludePair(Pair pair) {
    mates[pair.getFriendA() - 1] = false;
    mates[pair.getFriendB() - 1] = false;
  }

  public void includePair(Pair pair) {
    mates[pair.getFriendA() - 1] = true;
    mates[pair.getFriendB() - 1] = true;
  }

  public boolean isAnyoneLeft() {
    for (boolean isExist : mates) {
      if (isExist) return true;
    }

    return false;
  }

  public int getAmount() {
    int amount = 0;
    for (boolean isExist : mates) {
      if (isExist) amount++;
    }

    return amount;
  }
}

class Pair {
  private int friendA;
  private int friendB;

  public Pair(int friendA, int friendB) {
    this.friendA = friendA;
    this.friendB = friendB;
  }

  public int getFriendA() {
    return friendA;
  }

  public int getFriendB() {
    return friendB;
  }
}

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

문제

문제

출처

ICPC

시간 초과가 뜹니다. 어느 부분을 개선해야 할까요?

deepred 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말