tlov
[swea] 1859. 백만 장자 프로젝트 본문
문제: 1859. 백만 장자 프로젝트
날짜: 08/28 (수)
성공여부: O(댓글힌트)
그리디 문제이다. 그리디에 대한 준비가 안되어있어서 좀 어려웠다. 결론부터 말하면 배열을 뒤로 반복해서 풀면 풀리는 문제이다. 무조건 배열을 앞에서부터 반복할 필요가 없다는 생각을 해야한다.. 이게 참 쉬운데 어려운듯하다.
처음 풀이는 앞에서부터 반복하면서 현재 값에서 바로 뒤에 자기보다 작은 값이 나오면 현재 값을 기준으로 지금까지 산 물건들을 팔아 그 차액을 ret 변수에 더했다. 예제만 놓고보면 해당 로직에 문제가 없다. 그런데 아래 반례가 있다.
1 2 3 5 2 4 7 1
1 2 3 5 2 4까지 모두 산다음에 7에서 팔면 최대 이익!
그러나, 위의 로직대로 한다면 1 2 3 까지 산 후 5에서 모두 팔고, 다시 2 4까지 산 후 7에서 판매한다.
이런 반례를 생각못해서 댓글을 참고했고 뒤에서 풀면 된다고 해서 그 생각을 갖고 다시 풀었다.
배열의 뒤에서부터 배열의 원소를 가지고 max 값을 갱신하면서 max 값보다 작은 값들은 사놓고 max에서 판매하면 그때가 제일 이득을 볼 수있는 상황이니까 그 차액을 계산해 ret에 더해준다. 위의 예제를 예로 들면
1 2 3 5 2 4 7 1
처음에 max = 1
그리고 다음 원소로 가면 max < 7 이기 때문에 max = 7이 되고
이후부터는 계속 max > 4 or 2 or 5 or 3 or 2 or 1이다.
그럼 max 값에 해당 원소를 빼서 그 차액을 계속 ret에 더해주면 된다.
코드
import java.util.Scanner;
public class Solution {
static int[] gold;
static long ret;
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++)
{
int n = sc.nextInt();
gold = new int[n];
for (int i = 0; i < n; i++) gold[i] = sc.nextInt();
ret = 0;
int max = 0;
for (int i = n-1; i >= 0; i--) {
if (gold[i] > max) max = gold[i];
else ret += (max - gold[i]);
}
System.out.println("#" + test_case + " " + ret);
}
}
}
'알고리즘 문제' 카테고리의 다른 글
2156 - 포도주 시식 (0) | 2024.08.30 |
---|---|
1463 - 1로 만들기 (0) | 2024.08.29 |
2632 - 피자판매 (2) | 2024.08.25 |
17143 - 낚시왕 (0) | 2024.08.24 |
17406 - 배열 돌리기 4 [성공(반례힌트)|01:06:16] (0) | 2024.08.17 |