[D2] SWEA - 1859. 백만 장자 프로젝트 : Java

SW Expert Academy

 

 

문제

25년 간의 수행 끝에 원재는 미래를 보는 능력을 갖게 되었다. 이 능력으로 원재는 사재기를 하려고 한다.

다만 당국의 감시가 심해 한 번에 많은 양을 사재기 할 수 없다.

다음과 같은 조건 하에서 사재기를 하여 최대한의 이득을 얻도록 도와주자.

    1. 원재는 연속된 N일 동안의 물건의 매매가를 예측하여 알고 있다.
    2. 당국의 감시망에 걸리지 않기 위해 하루에 최대 1만큼 구입할 수 있다.
    3. 판매는 얼마든지 할 수 있다.

예를 들어 3일 동안의 매매가가 1, 2, 3 이라면 처음 두 날에 원료를 구매하여 마지막 날에 팔면 3의 이익을 얻을 수 있다.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스 별로 첫 줄에는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고,

둘째 줄에는 각 날의 매매가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다.

각 날의 매매가는 10,000이하이다.


[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 이익을 출력한다.


[예제 풀이]

1번째 케이스는 아무 것도 사지 않는 것이 최대 이익이다.

2번째 케이스는 1,2일에 각각 한 개씩 사서 세 번째 날에 두 개를 팔면 10의 이익을 얻을 수 있다.

입력
3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

출력
#1 0
#2 10
#3 5

 

 

 

풀이1

class Solution
{
	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[] arr = new int[sc.nextInt()];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextInt();
            }
            System.out.println("#" + test_case + " " + calculate(arr));
		}
	}
    
    private static long calculate(int[] arr) {
        long sum = 0;
        
        for (int i = arr.length - 1; i > 0; i--) {
            int cur = arr[i];
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] >= cur) {
                    i = j + 1;
                    break;
                }
                
                sum += cur - arr[j];
                
                if (j == 0) {
                    return sum;
                }
            }
        }
        
        return sum;
    }
}

• main()의 for문 내부에서 각 테스트케이스마다 arr라는 int 배열을 만든 후, calculate() 호출
• calculate()
  • sum : long 타입이어야 함 
    • N(2 ≤ N ≤ 1,000,000) X 10,000(각 날의 매매가) = 10,000,000,000(백억)
    • int 범위를 초과함
    • 테스트 케이스 7/10만 통과
  •  이중 for문 사용
    • cur은 현재 arr[i]의 값
    • 내부 for문
      • j는 i - 1부터 0까지
      • 만약 arr[j]가 cur보다 크거나 같은 값이라면
        • i를 j + 1로 설정 후 break
        • 이유 : i--라는 조건이 있기 때문
      • 그렇지 않다면 sum에 cur - arr[j]를 뺀 값을 더함
      • 이 때 만약 j == 0 (배열의 끝) 에 도달했다면 sum을 반환하며 종료
• 시간복잡도 : O(N^2)

💬 오로지 통과만을 목적으로 한 노가다 풀이 ㅎ...

 

 

 

풀이2

참고

[알고리즘|SWEA] 1859. 백만 장자 프로젝트(D2) Java

    private static long calculate(int[] arr) {
        long max = Long.MIN_VALUE;
        int count = 0;
        long cost = 0L;
        long result = 0L;
        
        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] > max) {
                result += (max * count - cost);
                max = arr[i];
                
                cost = 0L;
                count = 0;
            } else {
                cost += arr[i];
                count++;
            }
        }
        
        result += (max * count - cost);
        
        return result;
    }

• for문을 한 번만 사용
• max = 현재의 최댓값
• count = 사려는 주식의 개수
• cost = 사려주는 주식의 총합
• result = 결과
• 현재 max 값보다 큰 값이 나오면
  • max * count에서 cost를 뺀 값을 result에 더해준 후, max 값을 업데이트함
  • e.g. [3,5,9] 일 때, max가 9라면, cost는 3+5인 8, count는 2 → 9 * 2 - 8 = 10
  • cost와 count 초기화
• 그렇지 않다면
  • cost에 arr[i] 값 더하기
  • count++
• 마지막에 result += (max * count - cost) 를 한 번 더 해주어야 함
  • 이유
    • 만약 [3,5,9] 와 같은 배열이라면, max값을 한 번 9로 설정한 후, 다시 if 조건에 걸릴 일이 없음
    • 그렇다면 cost와 count를 쌓아만 두고, result는 한 번도 계산하지 못한 채 for문이 끝나게 됨
• rseult 반환
• 시간복잡도 : O(N)