그리디 알고리즘 (2) 썸네일형 리스트형 백준 1758 - 알바생 강호 www.acmicpc.net/problem/1758 1758번: 알바생 강호 첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수 www.acmicpc.net 고객이 기다리는 순번이 하나 증가할수록 주려는 팁에 패널티가 1씩 생길 때(역으로 돈을 갈취하지는 않는다.), 강호가 가장 많이 팁을 벌 수 있도록 하여 고객을 배치할 때 벌어들이는 팁을 구하는 문제이다. 높은 금액의 팁을 주는 고객일수록 적은 패널티를 받게 해야 최적해에 이를 수 있다. 따라서 팁을 많이 주는 순서대로 내림차순 정렬하여 받을 수 있는 팁을 계산하면 최적해를 구할 수 있다. .. [ICPC] 백준 17521 - Byte Coin www.acmicpc.net/problem/17521 자본금으로 얼마나 많은 수익을 얻을 수 있을지 구하는 문제이다. 바이트 코인 예측 금액을 나열한 차트를 단조 감소하는 구간과 단조 증가 하는 구간으로 분리하여 단조 감소를 만족하는 마지막 날에 풀매수하고 단조 증가를 만족하는 마지막 날에 풀매도하면 최대 이익을 얻을 수 있다. 단조 감소 구간을 추적하는 L 포인터와 단조 증가 구간을 추적하는 R 포인터를 통해 최적 매수/매도 날짜를 탐색한 후 이를 계산하는 방식으로 구현했다. 전체 코드 더보기 #include using namespace std; using ll = long long; int main() { int days; ll seed; cin >> days >> seed; if (days == 1.. 이전 1 다음
