[BOJ] 백준 5545 최고의 피자 (Swift)

문제

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

5545번: 최고의 피자

풀이

• 1원 당 열량이 가장 큰 피자가 최고의 피자이고 최고의 피자의 1원 당 열량을 구하는 문제
• 입력받은 토핑을 가장 큰 열량별로 정렬을 해주고, 1원 당 열량을 계산하는 방식으로 풀이할 수 있겠다고 생각이 듬
• 1원 당 열량을 계산하고, 다음 토핑을 추가했을 때, 1원 당 열량이 현재보다 크다면 토핑을 추가하고 아니라면 더 이상 토핑을 추가하지 않으면 될 것이다 라고 생각함

소스코드

	let n = Int(readLine()!)!
	let input = readLine()!.split(separator: " ").map { Int($0)! }
	let a = input[0], b = input[1]
	let c = Int(readLine()!)!
	var price: [Int] = []
	for _ in 0..<n {
	price.append(Int(readLine()!)!)
	}
	price = price.sorted(by: >)
	// d는 현재 추가된 칼로리
	var d = c
	// 토핑을 아예 추가하지 않는 경우도 있으므로 (현재 칼로리 / 도우 가격) 최초 값
	var answer = d / a
	for (index, price) in price.enumerated() {
	d += price
	let currentPrice = a + (b * (index + 1))
	// 현재까지 토핑을 추가했을 때, 1원 당 열량 보다 크거나 같다면 토핑을 추가해 줌
	// 작다면 더 이상 토핑을 추가하지 않음
	if d / currentPrice >= answer {
	answer = d / currentPrice
	} else {
	break
	}
	}
	print(answer)

view raw 최고의 피자.swift hosted with ❤ by GitHub

후기

• 소스코드 25번 줄의 조건을 크거나 같다가 아닌 "크다" 로 해서 틀렸습니다가 계속 나왔었다..
• Int 끼리의 몫을 구하는 것이므로 소수점 뒷 자리를 알 수 가 없었기에 크거나 같다로 조건을 변경해줘서 맞출 수 있었음
  • 만약 answer가 36.3 이고 다음 토핑을 추가했을 때 36.9가 되어도 둘다 36이기 때문에 토핑을 추가하지 않았었지만 이런 예외가 있음
• 이 문제가 그리디 알고리즘이라는 것을 판별할 수 있다면 쉽게 풀 수 있는 문제였지만, 예외사항을 떠올리기는 쉽지 않았던 문제였음