11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net ◎ 문제 풀이 산다 2) 판다 3) 아무것도 안한다. 3가지 경우가 있고 목표하는 n 날에 최대이익을 구하는 문제이니, 처음에는 DP를 발상하였다. 그러나 DP로 풀기에는 한계가 있었다. 주식을 하나 팔 수도, 두 개 팔 수도 있었다. DP로 이런 복잡한 경우의 수까지 고려할 수 없었다. 주식은 가장 쌀 때 사서 비쌀때 파는 것이다. 그러므로 그리디 알고리즘이 적합하다. 매일 주가를 기준으로 향후 가장 비싼 주가인 날에 팔면 된다. 주가를 내림차순으로..