[그리디] 백준 2875 - 파이썬

 

의식의 흐름 알고리즘은 문제를 보고 내가 첨에 든 생각들을 끄적인거라 틀린 알고리즘임.

답만 알고 싶다면 최종 알고리즘이나 정답코드만 보면 된다.

 

이제 그리디 알고리즘으로 진입!

 

백준 2875.

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

---

의식의 흐름 알고리즘

일단 문제를 읽고 해석 해보면 (여2, 남1)이 한 팀으로 구성.

인턴십 참가인원(k)는 대회참가불가능.

그러면 이제 고려해야할 점이 인턴십 참가인원 k는 여자/남자 중 어디에 얼마나 빼야할지를 고려해야한다.

그러기위해선 n , m의 비율을 먼저 확인해야 할텐데 (여2,남1) 구성이니

n : m이 2 : 1이 될 수 있는 최대값을 먼저 고려해보자. = 일단 구성될 수 있는 team수

 

예제1 처럼 6 3 인 경우는 이미 2:1이니 k(2)를 나눠서 빼주고

예제2 의 경우도 마찬가지

예제3의 경우는 6 10 으로 남자 7명은 필요가 없다. 그러면 k를 m 에서 다 빼버리고 팀 구성을 해주면 되겠다.

추가로 고려할 점은 6 5 3 정도로 어정쩡하게 제시되었을 때 겠는데

->마찬가지로 남자 2명은 일단 필요가 없고 1명 더는 어쩔 수 없이 아무 곳에서나 빼주면 되겠다.

반대로 10 2 3 과 같이 여자가 훨씬 많아서 여자가 남는 경우도 고려해줘야한다.

 

내가 구성한 방식은

1. 주어진 n, m을 가지고 나올 수 있는 최대 team수를 먼저 구한다.
2. 해당 team을 꾸리고 남은 사람들의 수를 구한다.
3. 남은 사람 수와, 인턴십에 참가해야하는 k 값을 비교하여
4. 남은 사람 수가 많다면 -> 최초 구한 team값을 결과값으로 보면 되고
5. 참가해야하는 사람 수가 더 많다면 -> 3명이 한팀 구성이기때문에 (k-rest)/3 을 했을 때 나머지가 있는 경우는 -1을 추가로 해줘야한다.

 

틀린답

def greedy2():
    n, m, k = map(int,input().split())
    res = 0   #결과값
    rest = 0  #최초 팀 구성 후 남는 인원
    team = 0  #최초 제시 n,m으로 만들 수 있는 팀 수

    if n >= m*2 :
        team = m
        rest = n - (m*2)
    else:
        team = n // 2
        rest = m - (n//2)
        
    if rest >= k:
        res = team
    else :
        res = team - ((k - rest) // 3) - 1
    print(res)

 

 

반례

흠 예시들은 다 통과했는데 어딘가 반례가 있나보다.

"4 2 3" 과 같은 경우를 잘 보자.

마지막 else처리에서(k-rest)로 3명씩 팀으로 만들어질 수 있는채로 빠지면 팀 구성이 정확하게 몫으로 빠지기 때문에 추가 -1을 해주면 안된다.

굳이 -1이 있는 이유는 이미 팀 구성이 다 된 상황에서 4명을 빼야하는 경우는 1팀하고도 1명이 어정쩡하게 남아 2팀이 빠지기 때문에 처리를 한 것이기 때문이다.

    else :
        if (k-rest) % 3 == 0:
            res = team - ((k - rest) // 3)
        else:
            res = team - ((k - rest) // 3) -1

 

다른 반례로 "15 8 11" 도 있다. 당연히 모두 짝수일 리가 없는데 너무 멍청하게 알고리즘을 짰다.

흠.. 이 예시로 봐서는 첫번째 else문에서 둘 다 홀수인 경우 n의 남은 인원도 계산하여 넣어줘야함을 알 수 있다.

else:
    team = n // 2
    rest = m - (n//2) + n - (team * 2)

 

 

 

최종 알고리즘

def greedy2():
    n, m, k = map(int,input().split())
    res = 0
    rest = 0
    team = 0

    if n >= m*2 :
        team = m
        rest = n - (m*2)
    else:
        team = n // 2
        rest = m - (n//2) + n - (team * 2)
        
    if rest >= k:
        res = team
    else :
        if (k-rest) % 3 == 0:
            res = team - ((k - rest) // 3)
        else:
            res = team - ((k - rest) // 3) - 1
    print(res)