[SWEA 1859][D2][JAVA] 백만장자 프로젝트

[문제]

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE

SW Expert Academy

 

[풀이방법]

 

처음에는 DP 푸는 방식처럼 [현재까지 계산한 이득 비용,  현재 가격 * 물건의 개수 -  이전 비용들의 합] 에서 큰 값을 계산해서 DP 배열에 저장한 후에 개 중 가장 큰 값을 구하려고 했더니 세번째 테스트 케이스가 맞지 않아 다시 생각해야 했습니다. 

 

3 5 9 -> 이 경우에는 첫째 날에 3을 지불하고 물건 1개를 구매합니다. (현재 사용한 비용 3 / 물건의 개수 1)

둘째 날에는 물건의 값이 5만큼 올랐으니 5 -3해서 2만큼의 이득을 얻었습니다. (현재 사용한 비용 5 / 팔았을 때 이득 비용 : 2 / 물건을 산 경우에는 물건의 개수 2)

셋째 날에는 물건의 값이 9만큼 올라서 18 - 8해서 10만큼의 이득을 얻었습니다. (이득 : 10 / 물건의 개수 0)

 

이렇게 마지막에 가장 큰 이득을 얻고 계산이 중지되는 경우에는 첫 번째 코드가 맞았지만 이 문제는 물건의 사고 팔고가 적절한 때에 이루어져야 한다는 것 핵심이었습니다. 

밑과 같은 경우에는 통하지 않습니다. 
1 1 3 1 2 -> 첫째 날에는 1을 지불하고 물건 1개를 구매합니다. (현재 사용한 비용 1 / 물건의 개수 1)

둘 째 날에는 1만큼 지불하고 물건 1개를 구매합니다. (현재 사용한 비용 2 / 물건의 개수 2)

셋째 날에는 2만큼 지불하고 물건 2개를 판매합니다. (이득 비용 4 / 물건의 개수 0)

 

바로 여기서 꼬여버립니다. 최대값을 구하기 때문에 최대 이득 비용인 셋째 날 4에서 더 이상 물건을 사거나 팔지 못하게 되어버리기 때문에정답을 제대로 도출할 수 없습니다.

 

사고 팔고를 계속해서 이어나가기 위해서는 가격을 최대 값으로 갱신한 후에 그 가격을 기준으로 물건을 사고 팔아야 합니다.

 

이 문제의 핵심은 뒤에서부터 최대값을 갱신하는데 있습니다.

 

맨 마지막 날의 비용을 최대값으로 두고 만약 오늘의 비용이 최대값보다 작은 경우에는 물건을 팝니다. (ans += max - cost[i])

만약 오늘의 비용이 최대값보다 크다면 그때는 최대값을 갱신합니다. (물건을 팔지 않는 경우입니다.)

 

 

            int ans = 0;
            int max = cost[N];
            
            for (int i = N-1; i >= 1; i--) {
                
                if (cost[i] < max) {
                    ans += max - cost[i];
                } else {
                    max = Math.max(cost[i], max);
                }
            }