본문 바로가기
Programming Test/문제풀이

[문제 풀이 5] 코드 트리 - 스승의 은혜

by muns91 2024. 4. 11.
스승의 은혜

 

  • 문제 유형 : 정렬, Exhaustive Search
  • 사용언어 : Python
  • 난이도 : 실버 3
  • 출처 : 코드 트리

 

https://www.codetree.ai/training-field/search/problems/the-grace-form-teacher?&utm_source=clipboard&utm_medium=text

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 

def find_max_gifts(N, B, gifts):
    # 선물을 반값 할인 받았을 때와 받지 않았을 때의 비용을 계산하는 함수
    def calculate_cost(index):
        return [gifts[i][0] + gifts[i][1] if i != index else gifts[i][0] // 2 + gifts[i][1] for i in range(N)]
    
    answer = 0
    # 모든 선물에 대해 반값 할인을 적용해보며 최대 명수를 찾는다
    for i in range(N):
        # i번째 선물에 대해 할인 적용 후 전체 비용을 계산
        costs = calculate_cost(i)
        # 비용이 낮은 순으로 정렬
        costs.sort()
        total_cost = 0
        count = 0
        # 예산 내에서 선물할 수 있는 최대 학생 수 계산
        for cost in costs:
            if total_cost + cost <= B:
                total_cost += cost
                count += 1
            else:
                break
        answer = max(answer, count)
    return answer

# 입력 예제
N, B = tuple(map(int, input().split()))

gifts = []

for _ in range(N):
    gifts.append(tuple(map(int, input().split())))

# 함수 호출
max_gifts_count = find_max_gifts(N, B, gifts)
print(max_gifts_count)
반응형