Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://www.acmicpc.net/problem/11501
11501번: 주식
입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타
www.acmicpc.net
풀이
solved.ac 난이도: Silver 2
간단한 그리디 알고리즘 문제.
주식은 낮을 때 사서 높을 때 팔아야하는 것처럼 해당 문제도 같은 방식으로 풀 수 있다.
주가를 입력받은 stock_value을 역순으로 진행하면서 두가지를 확인하면 쉽게 구할 수 있다.
1. 현재(day)의 주가가 지나온 주가 중에서 최대 주가(max_stock)보다 작다면
해당 주식은 구매해서 max_stock인 날에 팔아야 최대 수익을 낼 수 있다.
stock_sum += (max_stock - stock_value[day])
2. 현재(day)의 주가가 최대 주가(max_stock)크거나 같다면
해당 날에는 주식을 산다면 더 높은 가격으로 팔 날이 오지 않는다.
따라서 max_stock을 stock_value[day]으로 갱신해준다.
예를 들어 아래의 예제를 살펴보자.
10 7 6 100 1 3
day = 6 (max_stock=0)
3 => max_stock < 3 이므로 max_stock = 3
1
100
6
7
10
day = 5 (max_stock=3)
1 => max_stock > 1 , profit_sum = 2
100
6
7
10
day = 4 (max_stock=3)
100 => max_stock < 100 , max_stock = 100
6
7
10
day = 3 (max_stock=100)
6 => max_stock > 6 , profit_sum =96
7
10
day = 2 (max_stock=100)
7 => max_stock > 7 , profit_sum =189
10
day = 1 (max_stock=100)
10 => max_stock > 10 , profit_sum =289
추가적으로 profit_sum은 최대 10,000,000,000정도의 값을 가질 수 있으므로 long long형으로 선언해주자.
코드
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No.10165 - 버스 노선 (C++) (0) | 2021.01.07 |
|---|---|
| [백준] No.2513 - 통학버스 (C++) (0) | 2021.01.04 |
| [백준] No.7570 - 줄 세우기 (C++) (0) | 2021.01.02 |
| [백준] No.13904 - 과제 (C++) (0) | 2021.01.02 |
| [백준] No.1339 - 단어 수학 (C++) (0) | 2021.01.01 |