SWEA: 1859 백만 장자 프로젝트

문제 정보

---

SW Expert Academy

 

 

핵심

---

두 가지 풀이가 있는데, 앞에서부터 확인할 것인가 뒤에서부터 확인할 것인가 이다

 

결론부터 말하자면 이 문제는 뒤에서부터 확인하는 것이 훨씬 효율적이다

 

두 가지의 접근 방식에서의 풀이방식과, 내가 간과했던 부분을 바탕으로 풀이를 작성해 보겠다

 

 

풀이

---

1. Bottom-Up을 사용한 풀이

import java.io.*;
import java.util.*;

class Solution {
	static long result;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			int N = Integer.parseInt(br.readLine());
			List<Integer> array = new ArrayList<>();
			result = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			while (st.hasMoreTokens()) {
				array.add(Integer.parseInt(st.nextToken()));
			}
			int currentIndex = 0;

			while (currentIndex < N) {
				int maxNum = Collections.max(array.subList(currentIndex, N));
				for (int i = currentIndex; i < array.size(); i++) {
					if (array.get(i) == maxNum) {
						currentIndex = i + 1;
						break;
					}
					result += maxNum - array.get(i);
				}
			}
			System.out.println("#" + test_case + " " + result);
		}
	}
}

- 일단 모든 물건은 가장 최대 가격에 파는 것이 이득이다 (하루에 하나만 구매할 수 있지만, 파는 개수는 제한이 없기 때문이다)

- 물건을 구매하기 전에는 판매할 수 없기 때문에, 현재 인덱스를 기준으로 끝 인덱스까지의 최대값을 구하고 그날에 팔아야 한다

 

1. 먼저 현재 위치부터 끝 위치까지의 최대값을 구하고 maxNum에 저장한다

2. 최대값이 위치한 인덱스까지 모든 물건을 사고, maxNum이라는 가격에 팔아간다

3. 최대값이 위치한 인덱스에 도착하면, 그 다음 위치부터 끝 위치까지의 최대값을 다시 구하며 1-2 과정을 반복한다

3-1. 다음에 위치하는 이유는, 해당 위치가 최대값이기 때문에 판매해도 이윤을 남길 수 없기 때문이다

 

 

2. Top-Down을 사용한 풀이

import java.io.*;
import java.util.*;

class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            List<Integer> array = new ArrayList<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                array.add(Integer.parseInt(st.nextToken()));
            }

            System.out.println("#" + test_case + " " + solution(N, array));
        }
    }

    public static long solution(int N, List<Integer> array) {
        long result = 0;
        int max_sell = array.get(N - 1);
        for (int i = N - 2; i >= 0; i--) {
            int indexedItem = array.get(i);
            if (indexedItem >= max_sell) {
                max_sell = indexedItem;
            } else {
                result += max_sell - indexedItem;
            }
        }
        return result;
    }
}

- 뒤에서부터 탐색하면, 리스트의 모든 부분에서의 최대가격을 구할 필요 없이 시작 지점(끝)부터 현재 인덱스까지만 생각하면 된다

- 반대로 순회하면서, 현재까지의 최대 가격보다 크다면 구매하지 않고 최대 가격으로 지정하며 작다면 구매하고 이윤을 더해준다

 

1. 최대값을 가장 끝 인덱스의 가격으로 지정한다

2. 다음 위치부터, 최대 가격보다 낮은 경우 팔고 높은 경우 판매하지 않고 최대 가격만 올린다

2-1. 팔지 않는 이유는, 현재 인덱스가 최대 가격인 경우 지금까지 나왔던 가격들은 모두 현재 인덱스보다 낮은 가격이기 때문에 판매해도 이윤이 남지 않는다

 

 

고찰

---

간과했던 부분

1,000,000 일 동안의 매매가가 나올 수 있으며 각 날의 매매가는 10,000 까지 나올 수 있다

매매가의 총 합을 계산하다 보면 int의 표현범위를 넘어가서 값이 비정상적으로 저장될 수 있기 때문에

long을 사용하여 이를 저장하여야 한다는 것을 간과했다

 

Source Code on GitHub

---