1859. 백만 장자 프로젝트

테스트케이스.zip

6.41MB

D2에 해당하는 문제중에 정답률이 20%대 인만큼 가장 어려운 문제인 것 같습니다..  한번에 Pass하긴 했으나 정확히 풀려고 하다보니 솔직히 푸는데 5시간은 걸린 것 같습니다. 그래도 어려운 문제를 풀었을 때 사고력도 높아지고, 그 성취감이 있기에 또 푸는게 아니겠습니까? ^^

 

문제:

 

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의 이익을 얻을 수 있다.

 

 

해설: 이 문제는 물건을 최대한 싸게사서 최대가에 모두 팔아서 이익을 극대화시키는 문제입니다. 따라서

구입시기는 최대값보다 작은 시기이고, 판매시기는 최대값이 나오는 시기입니다.

그러면 이익은 최대값*cnt - sum이 되고 이것을 bnf에 누적합니다.

그리고 최대값 다음 인덱스부터 다시 두번째 최대값을 구해주고, 그 이전까지의 합을 누적합니다.

그리고 다시 이익을 구하고, res가 gets보다 작은 순간동안만 계속 반복해줍니다.

그리고 gets가 커짐에 따라 sum과 bnf가 6억을 넘어가기 때문에 sum, bnf, max는 반드시 long형으로 정의해줍니다.

이것이 주의사항 입니다.

 

* 코드

import java.util.Scanner;
import java.util.ArrayList;
import java.io.FileInputStream;

class Solution {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		ArrayList<Integer> arr = new ArrayList<>();
		long[] ansArr = new long[100];
		int maxidx = 0;
		long sum = 0;
		long bnf = 0;
		long cnt = 0;
		int res = 0;
		long max = 0;
		int gets;
		
		int T = sc.nextInt(); // 테스트케이스

		for (int test_case = 1; test_case <= T; test_case++) {
			
			gets = sc.nextInt(); // 원소 갯수
			for (int i = 0; i < gets; i++)
				arr.add(sc.nextInt());

			while (res < gets) { //재시작 인덱스는 배열원소수를 넘을 수 없다.

				for (int i = res; i < gets; i++) { // 재시작인덱스부터 끝까지 최대값을 구함
					if (max < arr.get(i)) {
						max = arr.get(i);
						maxidx = i;
					}
				}

				for (int i = res; i < maxidx; i++) { // 재시작인덱스부터 최대값 전까지 더함
					sum += arr.get(i);
					cnt++;
				}

				bnf += (arr.get(maxidx) * cnt - sum); //이익을 누적함
				cnt = 0;
				sum = 0;
				res = ++maxidx; // 재시작 인덱스는 최대값 인덱스 보다 1이 큼

				if (res < gets) // 재시작인덱스가 원소 수보다 작을때만,
					max = arr.get(res); // 최대값을 갱신해줍니다.
			}

			ansArr[test_case-1] = bnf; // 배열에 차례차례 이익값 넣어줌
			bnf = 0; // 변수 모두 초기화
			cnt = 0;
			sum = 0;
			res = 0;
			max = 0;
			maxidx = 0;

			arr.clear(); // **arr 클리어 반드시 해줘야함, 이후 값에 영향을 줌
		}

		for (int i = 0; i < T; i++) {
			System.out.println("#" + (i + 1) + " " + ansArr[i]); // 출력
		}

	}
}