Algorithm) BOJ) 백준 2875 - 대회 or 인턴

문제보러가기

1. 초기접근

문제 조건 해석

여자 > 남자x2 이면, 남자의 수 = 팀

아니면, 여자/2 = 팀

이후에 남자든 여자든 어느 한쪽은 모두 팀을 이뤘기 때문에 k에서 나머지 인원만큼을 뺀다.

아직 k가 남아 있다면 3명 단위로 빼줘서 구해나갈 수 있다.

 

알고리즘

총 3가지 방법이 있다.

1. 1. 팀을 이룰 수 있는 3가지 경우

문제 해석에서 봤던 남자의 수, 여자/2의 수 + (전체인원 - 인턴의 수)/3

3개 중에 가장 적은 수가 가능한 팀이 된다.

 

2. 2. 남자가 모두 팀을 이루거나, 여자/2가 모두 팀을 이루거나

문제 해석까지 생각한 다음, k가 남아 있다면 팀에서 k/3을 빼고,

아직도 팀이 남아있다면 1을 한번 더 빼준다. (3명을 넘지 않을 것이기 때문에)

 

3. 3. 인턴을 남자에서 시킬지, 여자에서 시킬지

여자/2가 남자보다 크거나 같다면 여자 중에서,

아니라면 남자 중에서 인턴을 보낸다.

 

2. 회고

여러가지 방법이 있다.

가장 멋있고 효율적인 코드는 1번 같지만 쉽게 생각할 수 있을지는 모르겠다.

그리디 방법에 가장 가까운 것은 3번이 아닐까 싶다.

2번은 내가 생각했던 방법인데.. 여러 분기처리를 하기보다 그리디가 가능한 경우의 수라면 그리디로 푸는 것이 더 좋을 것 같다. 강력한 그리디에 익숙해지고, 그리디가 안된다면 효율적인 코드를 생각해보자.

3. 코드

guard let inputs = readLine()?.split(separator: " ") else { fatalError() }

guard var w = Int(inputs[0]) else { fatalError() }
guard var m = Int(inputs[1]) else { fatalError() }
guard var k = Int(inputs[2]) else { fatalError() }
var team = 0

// MARK: solution 1
print(min(w/2, m, (w+m-k)/3))


// MARK: solution 2
if (w/2) >= m {
    team = m

    k -= w - team*2

    if k > 0 {
        team -= k/3

        if k%3 > 0 {
            team -= 1
        }
    }

} else {
    team = w/2
    k -= m - team

    if k > 0 {
        team -= k/3
        
        
        if k%3 > 0 {
            team -= 1
        }
    }
}

team >= 0 ? print(team) : print(0)

// MARK: solution 3
while k > 0 {
    k -= 1
    
    if w/2 >= m {
        w -= 1
    } else {
        m -= 1
    }
    
}

print(w/2 >= m ? m : w/2)