2 분 소요

[공지사항] 알고리즘 카테고리 포스트 살펴보기

:rocket: 문제 설명

백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.

여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.



:rocket: 내 풀이

첫번째 접근 방식

처음에는 별 생각없이 브루트포스 비슷한 방식으로 시도했다.

지금 생각하면 참 비효율적이지만, 놀랍게도 시간 제한에 통과하더라.

아마 낮은 난이도의 문제여서 시간 제한이 널널하게 잡힌 것은 아닐까 싶다.

내 첫번째 풀이는 다음과 같다.


import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N, M, K;

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        int maxTeam = 0;
        for (int i = 0; i <= K; i++){
            int girl = N - i;
            int boy = M - (K - i);

            int team = 0;
            while ((team + 1)* 2 <= girl && (team + 1) <= boy){
                team++;
            }

            maxTeam = Math.max(maxTeam, team);
        }

        bw.write(Integer.toString(maxTeam));
        bw.flush();
    }

}

인턴에 참가하는 학생을 남학생 집단에서 뺄지, 여학생 집단에서 뺄지 계산하는게 관건이었는데,

나는 아주 명석하게도 모든 경우의 수를 다 테스트하는 방식으로 접근했다.

인턴에 참가하는 학생을 뺀 이후에는 팀의 개수를 하나씩 늘려가며 남는 학생수를 비교해가며 최대 구성가능한 팀을 구했다.

각 경우의 수마다 최대 구성가능한 팀 수를 구해 maxTeam과 비교하여 가장 최대값을 저장하도록 했다.

그 결과 브루트포스 반복문 안에 while 반복문이 들어간 아주 비효율적인 코드가 작성되었다.

비효율적인 접근 방식에다가 심지어 이중반복문까지 사용해가며 굴렸지만, 어찌저찌 통과한 코드이다.

다른 사람들이 어떻게 풀었는지 알아보기 위해 검색하다가 문제를 깨달았다.




두번째 접근 방식

내 두 번째 접근 방식은 다음과 같다. 

import java.util.*;
import java.io.*;




public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N, M, K;

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());


        int maxTeam = 0;
        while (true){
            N -= 2;
            M -= 1;
            maxTeam++;
            if (N < 0 || M < 0 || (N + M) < K ){
                maxTeam--;
                break;
            }
        }
        bw.write(Integer.toString(maxTeam));
        bw.flush();
    }

}

입력 받는 부분은 똑같지만 훨씬 깔끔하고 직관적이다.

중요한 것은 최대 구성가능한 팀 수를 의미하는 maxTeam 변수이다.

maxTeam 변수를 0에서부터 늘려가면서 팀이 구성되지 않은 학생 수만 N과 M에 남겼다.

그러면서 매 반복마다 다음 조건을 충족하는지를 테스트했다.

  • 남은 여학생 수가 0보다 큰가?
  • 남은 남학생 수가 0보다 큰가?
  • 남은 전체 학생 수가 K보다 크거나 같은가? (인턴에 참가할 학생 수가 남아있는가?)

만약 조건을 충족하지 못한다면 이전 반복의 maxTeam이 최대 구성가능한 팀 수라는 것이다.

참고