[Algorithm] 백준_대회 or 인턴_2875번 (JAVA)

📝문제

https://www.acmicpc.net/problem/2875

 

💡풀이

며칠 전에 풀려고 시도했다가 아이디어가 안 떠올라 포기했던 문제를 다시 도전해보았다.

내 아이디어는 다음과 같다.

 

1)

대회에 나가는 여학생을 변수 a로,

대회에 나가는 남학생을 변수 b로 잡는다.

 

2)

전체 여학생 인원이 N이고

전체 남학생 인원이 M이므로

(N-a)+(M-b) 는 인턴을 나가는 학생 수보다 같거나 커야한다.

 

3) 

만약 N-a가 2보다 크거나 같고 M-b가 1보다 크거나 같으면 

대회에 나가는 학생의 수를 추가해줄 수 있다.

a = a + 2

b = b + 1

 

4) 3번의 조건식에 맞지않는다면 대회에 나가려는 학생에 비해 나갈 수 있는 학생이 적기 때문에 팀을 꾸릴 수 없으므로 반복문을 빠져나온다.

 

전체풀이

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int a = 0; //대회에 나가는 여학생
        int b = 0; //대회에 나가는 남학생

        int team = -1;
        while((N - a + M - b) >= K){
            team++;
            if((N-a) >= 2 && (M-b) >= 1){
                a += 2;
                b += 1;
            }else{
                break;
            }
        }
        System.out.println(team);
    }
}

 

🤔Review

그리디는 번뜩 떠오르는 아이디어가 중요한 거 같다