[알고리즘] BOJ 2875번 - 대회 or 인턴(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

4 / 50(NEW!)

 

탐색

3 / 50

 

기초 동적 프로그래밍

4 / 50

 

투포인터

0 / 10

---

문제

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

2875번: 대회 or 인턴

→ solved.ac 기준 브론즈 3 문제

---

문제 해결 아이디어

100명, 100명, 200명이 입력받았다고 했을 때

만약 다 참여한다고 가정하면 50팀이 된다.

(이 때 여자는 100명, 남자는 50명)

그러나 인턴십에는 200명이 필요하다.

50팀을 제외하고 남은 인원은 50명.

그래서 결성된 팀 중에 150명이 빠져야 한다.

빠진 인원이 150명이 될 때까지 team 인원을 뺀다.

---

구현

내 풀이

n, m, k = map(int, input().split())

team = min(n // 2, m)

# 팀에서 제외된 남은 인원 구하기
remain = n - team * 2 + m - team

# 빠져야 하는 인원이 0명이 될 때까지
while k > remain:
  team -= 1
  remain += 3
  
print(team)

n, m, k = map(int, input().split())

team = 0

# 처음 구현한 잘못된 로직
# while n + m > k:
#   n -= 2
#   m -= 1
#   if n < 0 or m < 0:
#     break
#   if n + m <= k:
#     break
#   answer += 1

# 다른 사람 구현 참고해서 만든 올바른 로직
while True:
  n -= 2
  m -= 1
  if n < 0 or m < 0:
    break
  if n + m < k:
    break
  answer += 1

print(answer)

---

메모

• 걸린 시간: 40분
• 반례 찾는데 너무 오래 걸린 문제
  
  • 처음 구한 로직이랑 비교하니 한끗차이..
• 반례 찾기.. 너무 어렵다

---

마치며

브론즈 문제여서 금방 끝날 줄.. 알았는데 아니었음

분류는 수학 & 구현 & 사칙 연산인데 대부분 포스팅에서 그리디로 분류했고,

문제 알게 된 경로도 그리디 알고리즘 추천 문제로 알게 되서 그리디 문제로 생각하고 +1 해따