문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE
(로그인 해야볼수있듬!)
해결 방법 :
쉬운난이도 문제라고해서 풀어보았는데, 하도 안풀려서 다른 사람의 힌트를 얻고 겨우 풀어낸 문제....
이 문제의 핵심은 최대이득을 구하기위해서는 사고팔고를 적절히 해야하는 방법을 생각해야하는데
그 방법이 맨뒤에서 부터 처음까지 도는 가운데 최대가격의 값을 기준으로 이득이 생기는 부분의 총합을 더하는 것이었다.
내가 헤맨것이 모든 가격을 내림차순으로 최대값순으로 새로운 배열을 만들고 만든 배열과 주어진 가격 배열을 하나씩 비교해 나가면서 더해나간게 문제였다.
예시의 테스트케이스는 다 통과되서 아 이게 맞다라고 생각하고(답정) 한게 큰 패인이다..
1 1 4 5 2 1 이 테스트케이스만 보더라도 5 4 2 1 1 1 이런 새로운 배열과 하나씩 비교할텐데, 4가 5안에 포함되어버려 이미 계산이 끝낫지만 여전히 새로운 배열에 비교 대상으로 존재해있어서 뒤에 2, 1 부분도 계산을 해준것이기 때문이다 ...
엄청난 뻘짓을 하고나서 힌트를 본후 , 대부분 사람들은 뒤에서 부터 계산을 해서 답을 찾았다는 것을 보았고,
아 그럼 뒤에서 부터 최대값을 갱신해주고 그 최대값보다 작으면 계속더해가는 방식이 모든 경우를 해결해 줄 수 있다는 것을 알게되었다.
위의 1 1 4 5 2 1 을 보면
맨뒤의 1을 max로 둔다.
그리고 맨뒤에서부터 처음일때까지 전부 비교해준다.
만약 현재 max 보다 크다면 max만 갱신해준다.
아니라면 max값보다 작으므로 이득을 더해나가준다.
이렇게 전부 계산해주고나면, 이득생기는 부분을 전부더해줘서 최대이득을 구할 수 있게된다.
소스코드)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include<iostream> long long max_margin = 0; int cost[1000001]; using namespace std; int main() { int test_case; cin >> test_case; for (int t = 1; t <= test_case; t++) { max_margin = 0; int max_price; int n; cin >> n; for (int i = 0; i < n; i++) { scanf("%d", &cost[i]); } max_price = cost[n - 1]; for (int i = n - 2; i >= 0; i--) { if (max_price > cost[i]) { max_margin += max_price - cost[i]; } else { max_price = cost[i]; } } printf("#%d %lld\n", t, max_margin); } } | cs |
'PS > SWEA' 카테고리의 다른 글
| 5986번 새샘이와 세 소수 (0) | 2018.11.03 |
|---|---|
| 2007번 패턴 마디의 길이 (0) | 2018.10.16 |
| 5550번 나는 개구리로소이다 (0) | 2018.10.06 |
| 1926번 간단한 369게임 (0) | 2018.10.05 |
| 1868번 파핑파핑 지뢰찾기 (0) | 2018.09.30 |