[구름톤 챌린지 #15] 과일 구매

2023. 9. 1. 23:12· 알고리즘/9oormthon Challenge
목차
  1. 문제 해결 방법

문제15. 과일 구매

 

구름LEVEL

난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.

level.goorm.io



문제 해결 방법

오늘 문제에서 가장 주의 깊게 보아야할 조건은 바로 "과일을 조각 단위로 구매하는 것이 가능하다"는 조건이다. 이 조건이 없었다면, 과일들의 가격이 다르고, 과일마다 포만감이 다르기 때문에 그리디 알고리즘을 적용할 수 없다. 그럴때는 완전탐색이나 DP 등의 알고리즘을 적용해야 풀 수 있는 문제였을 것이다.

 

하지만 오늘 문제에는 "과일을 조각 단위로 구매하는 것이 가능하다"는 조건이 있다. 과일을 조각 단위로 구매한다면 가격이 p인 과일 하나를, 가격이 1인 p개의 과일 조각으로 나눌 수 있다. 그리고 이때의 각 과일 조각의 포만감은 c/p가 된다. 이제는 가격이 모두 1로 동일한 과일 조각들이 있을 때, 과일 조각들로 얻을 수 있는 최대 포만감을 구하는 문제로 변환할 수 있다. 이제는 가장 포만감이 높은 과일 조각을 먼저 고르는 그리디 알고리즘을 적용할 수 있는 문제가 되었다.

 

위의 아이디어를 조금만 더 발전시켜보면, 모든 과일을 조각내는 대신, 가격 당 포만감이 가장 높은 과일부터 통째로 먹되 남은 돈으로 해당 과일을 통째로 먹을 수 없는 상황이 되면, 남은 돈으로 그 과일을 몇 조각 사면 된다.

 

위 내용을 코드로 구현하면 아래와 같다.

import sys

n, k = map(int, sys.stdin.readline().split())

pc_arr = []

for i in range(n):
    p, c = map(int, sys.stdin.readline().split())
    c_divided_by_p = c // p
    pc_arr.append([c_divided_by_p, p, c])

#c_divided_by_p가 낮은 순서대로 정렬 (뒤에서부터 pop할거임)
pc_arr.sort()

result = 0
while True:
    #돈이 남아도 과일이 없으면 못삼
    if not pc_arr:
        break

    #가격 당 포만감이 가장 높은 것부터 먹어야함
    fruit = pc_arr.pop()

    #현재 과일을 다 먹을 수 없다면 현재 과일을 조각으로 먹을 수 있음
    if fruit[1] > k:
        result += k * fruit[0]
        break
        
    k -= fruit[1]
    result += fruit[2]

print(result)

'알고리즘 > 9oormthon Challenge' 카테고리의 다른 글

[구름톤 챌린지 #17] 통신망 분석  (0) 2023.09.05
[구름톤 챌린지 #16] 연합  (0) 2023.09.04
[구름톤 챌린지 #14] 작은 노드  (0) 2023.08.31
[구름톤 챌린지 #13] 발전기 (2)  (0) 2023.08.30
[구름톤 챌린지 #12] 발전기  (0) 2023.08.29
  1. 문제 해결 방법
'알고리즘/9oormthon Challenge' 카테고리의 다른 글
  • [구름톤 챌린지 #17] 통신망 분석
  • [구름톤 챌린지 #16] 연합
  • [구름톤 챌린지 #14] 작은 노드
  • [구름톤 챌린지 #13] 발전기 (2)
young_and_mini
young_and_mini
young_and_mini
난아직어리고작아
young_and_mini
전체
오늘
어제
  • 분류 전체보기 (26)
    • 알고리즘 (24)
      • 백준(BOJ) (4)
      • 9oormthon Challenge (20)
    • 프로그래밍 언어 (2)
      • Python (2)
      • Java (0)
    • CS 전공지식 (0)
    • 백엔드 개발 (0)
    • 프론트엔드 개발 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 완전탐색
  • 시뮬레이션
  • shallow copy
  • 문자열
  • dp
  • deep copy
  • dfs
  • 그리디
  • BFS
  • 그래프
  • 투포인터
  • 구현
  • 구름톤트레이닝
  • 구름톤챌린지
  • Python
  • 후기

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
young_and_mini
[구름톤 챌린지 #15] 과일 구매
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.