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

오랜만에 알고리즘을 풀었다. 접속자체가 너무 오랜만이라 SW Expert Academy 휴면계정을 해제할 정도였다. 가볍게 D2 부터 시작하기 !

1859. 백만 장자 프로젝트

📖문제

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

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

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

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

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

🔍코드(Java)

		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int Tc = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= Tc; tc++) {
			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N];
			
			String line = br.readLine();
			StringTokenizer st = new StringTokenizer(line," ");	//공백단위로 값 분리
			
			//arr에 입력값 담기 - 매매가
			for (int k = 0; st.hasMoreTokens(); k++) {
				arr[k] = Integer.parseInt(st.nextToken());
			}
			
			int len = arr.length;
			
			//뒤에서부터 큰값이 나오면 리셋하기.맨뒤에 값이 무조건 큰값이라고 가정하기
			long max = Long.MIN_VALUE;
			int num = 0;
			long cost = 0L;		//구매가
			long result = 0L; 	//최종
			for (int i = arr.length-1 ;  i >= 0 ; i--) {
				// 더 큰 최댓값을 찾았다면? 호다닥 사자 ! 비용계산하기 : 사야할 애들의 갯수  * 판매가  - 구매가
				if( arr[i] > max ) {
					result += (max*num - cost);
					max = arr[i];
					//초기화
					cost = 0;		
					num = 0;
				}else {	//max 보다 작으면 사자
					cost+=arr[i];
					num++;
				}
			}
			
			//마지막에 한번 더 해주기
			result += (max*num - cost);
			
			System.out.println("#" + tc + " " + result);
		}// Tc

💡풀이

배열 맨 뒤에서부터 최댓값 찾기가 포인트.
최댓값보다 작은 값이면 구매하고, 더 큰값이 나오기 전까지 정산하는것을 반복하면된다. 배열을 다 돌면, 더이상의 최대값은 없으므로 마지막 정산까지 해주면 끝.

자꾸 TC중에 7개만 맞췄다고 해서 댓글을 슬쩍 참고했다.
N의 범위가 (1<= N <= 1,000,000) 이고 , 매매가의 최대값은 10,000 였다.그러면 최대 1,000,000 * 10,000 = 10,000,000,000 (백억?!)나올수있기때문에 int의 범위가 넘어가버리게 된다.

int java.lang.Integer.MAX_VALUE : 2147483647 [0x7fffffff]
A constant holding the maximum value an int canhave, 2^31-1.

그래서 금액을 long으로 변경해주니, 모든 TC에 통과하였다. 기본의 중요성을 깨달았다.