SW Expert academy 백만장자프로젝트 [자바]

 

---

 

나타날수 있는 공식 3가지

1. 10 7 6     // 마지막 까지 작아져서 사는게 손해

2. 3 5 9       // 마지막이 제일 값이 높아 마지막 전까지 사놓고 마지막에 팔기

3. 1 2 3 1 2   // 1 2 사고 3에 2개 팔고 그 다음 1에 사고 2에 팔고

 

tip

 1) Recursion을 이용하자

 1) 가장 높은 값은 미리 Array.sort()를 통하여 높은값 변수에 두고 선언한다.

 2) for문을 돌며 가장 높은값을 찾는다. (But 높은 값이 첫번째 일 경우 그 값을 빼고 다시 계산) 

 

1. 응용 // 큰 값이 첫 번째

Recursion 이용

// 큰 값이 첫 번째로 계속 나올경우 이익이 없음 0원

 

2. 응용  // 큰 값이 마지막

2개를 샀으니 9일때 샀던 2개를 9원에 팔수가 있음.

// 큰 값이 마지막이다? max값 == length-1 -> 바로 return 이익;

 

3.응용  // 큰 값이 중간 

 

---

-코드-

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

class Solution
{
	public static void main(String args[]) throws Exception
	{
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int j=1; j<=t; j++){
			int[] num = new int[sc.nextInt()];
        	for(int i=0; i<num.length; i++){
        		num[i] = sc.nextInt();
        	}
        	long a = rote(num);
        	System.out.println("#"+j+" "+a);
        	}
	}
    public static  long rote(int[] number){
        int[] num = number;
    	int[] fake = new int[num.length];
        for(int i=0; i<num.length; i++){
        	fake[i] = num[i];
        }
        Arrays.sort(fake);    // 위의 int[] fake = number를 하게 되면 주소로 연결 되기 때문에 Array 할 시 num배열도 같이 값이 바뀌게 됨 
        int max = fake[fake.length-1];
        
        long sum =0;
        long plus =0;
        for(int i=0; i<num.length; i++){
            if(num.length == 1) //배열이 1개 
                return 0;
            if(num[0] == max){ //1.큰값이 첫번째일 경우
            	int[] new_i = new int[num.length-1];
                for(int j=0; j<new_i.length; j++){
                		new_i[j] = num[++i];
                }
                return plus+rote(new_i);
            }else if(num[i] == max){
                	plus += i*num[i]-sum;
                	if(i != num.length-1){ //3.큰값이 마지막이 아닐경우만 
                		int[] new_i = new int[num.length-1-i];
                		for(int j=0; j<new_i.length; j++){
                			new_i[j] = num[++i];
                		}
                        return plus+rote(new_i); //2. 큰 값이 마지막이면 바로 return
                	}
                	return plus;
            }else{ // 큰 값 만날때 까지 더하는 경우
                sum += num[i];
            }
        }
        return 0;
    }
}