그리디14 [그리디 #8] BOJ 1758 - 알바생 강호 https://www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같 www.acmicpc.net 접근 방법 그리디의 정석으로 풀 수 있는 문제 중 하나이다. 이 문제에서 주문금액 - (등수 - 1)의 공식을 이용해 최고의 팁을 받는 것이 문제의 끝이다. 별다른 조건은 없기 때문에 주문금액이 가장 큰 손님부터 받게되면 팁을 최대로 챙길 수 있다. 쉽게 접근할 수 있는 문제라고 생각한다. 구현 시, N이 최대 100,000, 팁이 100,000을 넘을 수 있기 때문에 타입 선정.. 2024. 2. 11. [그리디 #7] BOJ 13305 - 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 접근 방법 예제 1을 살펴보자. 여기서 중요한 점을 체크해봤다. 1. 첫번째 도시에선 무조건 기름을 구입해야한다. 2. 마지막 도시의 기름값은 무시한다. 3. 현재 도시에서 다음 도시들 중 현재 도시의 기름값보다 싼 도시까지 가는 기름만 구매한다. (2에서 4를 거쳐 1로 가는 과정에서 2보다 싼 도시까지가는 거리의 기름을 산다.) 예를 들어 2 4 5 1 3 이런 도시가 있다고할 .. 2024. 2. 10. 이전 1 2 3 다음
