[SWEA #1859] 백만 장자 프로젝트 - JAVA(자바)

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

풀이:

ex) 3일 동안 매매가가 1 2 3

arr 배열에는 {0, 1, 1} 이 저장된다. 이때 arr[2]는 2일날 구매하고 3일날 판매했을 때 이익이다. arr[1] + arr[2]는 1일날 구매하고 3일날 판매했을 때 이득이다.

 

ex) 3일 동안 매매가가 3 1 2

arr 배열에는 {0,-2,1} 이 저장된다. 이때 arr[2]는 2일날 구매하고 3일날 판매했을 떄 이익이다. arr[1] + arr[2]는 1일날 구매하고 3일날 판매했을 때 이득인데 음수여서 이익을 볼 수 없다. 따라서 두번째 for문에 if(tmp >= 0) 조건이 있다.

 

최악의 경우를 선택하면

n = 1,000,000 이고 n일 동안 매매가가 (0,10,000, 0, 10,000, ...) 일 때

500,000 * 10,000 = 50억이 돼서 int 범위를 넘는다. 따라서 ans, tmp의 type을 long으로 해야 한다.

 

코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

    public static void main(String[] arges) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int testcase = Integer.parseInt(br.readLine());
        for(int t = 1; t <= testcase; t++){
            long ans = 0;
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n]; // arr[i]: i+1일 매매가 - i일 매매가
            StringTokenizer st = new StringTokenizer(br.readLine());
            int before = 0;
            for(int i = 0; i < n; i++) {
                int cur = Integer.parseInt(st.nextToken());
                if(i != 0){
                    arr[i] = cur - before;
                }
                before = cur;
            }
            long tmp = 0; 
            for (int i = n - 1; i >= 1; i--) {
                tmp += arr[i];
                if(tmp >= 0){
                    ans += tmp;
                }else{
                    tmp = 0;
                }
            }
            sb.append("#").append(t).append(" ").append(ans).append("\n");
        }
        System.out.println(sb);
    }
}