SW Expert Academy 1859. 백만 장자 프로젝트- 난이도 D2

-링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc 

SW Expert Academy

-문제

원재라는애가 물건을 사재기한담에 되팔이해서 이익을 보려고함..

근데 얘가 초능력이 있어서 어떤날에 그 물건이 얼마에 팔리는지 알수있음ㄷㄷ

얘를들어서 

3일동안 물건을 사고 판다고 할때 각 날짜별 물건 값이

3 5 9 이다

그러면 원재는 1일에 3원으로 물건을 하나 사고 2일에 5원으로 물건을 하나 산다

그리고 마지막날에 두개의 물건을 18원으로 팔면 18-8=10 10의 이익을 본다

이렇게 최대 이익을 계산해서 출력하라.. 는 문젠데..

이 문제 .. 어디서 많이 본 문제다 ㅋㅋㅋ 대외비가 있어 말은 안하지만.. 어디서 봤다.. 완전 같지는 않지만.. 비슷함

이문제 왜 난이도가 d2밖에 안하는지? ㅋㅋ?? 어려운데?

---

-아이디어

단순하게 생각해보면.. 일단.. 가격이 max인 날짜를 하나 찾는다

그리고 max이전의 날짜에서 일단 물건을 다 산다

max이후의 날짜들에서 다시 max를 찾고 그 날짜 이전에서 다 사고 두번째 max날에 판다

이런식으로 하면 되지 않을까? 말곤 딱히 안떠오름

---

-첫번째 코드: 위 아이디어대로 만듦->7개 맞았고 3개 틀림

import java.util.*;
class Solution
{	
	private static int margin=0;
	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 maxPrice=-1;
			int maxPriceIdx=-1;
			int days=sc.nextInt();
			int[] price=new int[days];
			for(int i=0;i<days;i++) {
				price[i]=sc.nextInt();
				if(price[i]>maxPrice) {
					maxPrice=price[i];
					maxPriceIdx=i;
				}
			}
			getMargin(maxPriceIdx,price);
			System.out.println("#"+test_case+" "+margin);
			margin=0;
		}
	}
	private static int[] cutArray(int start, int[] original) {
		int [] cut=new int [original.length-start];
		for(int i=start;i<original.length;i++) {
			cut[i-start]=original[i];
		}
		return cut;
	}
	private static int getMaxIdx(int[] list) {
		int idx=-1;
		int max=-1;
		for(int i=0;i<list.length;i++) {
			if(list[i]>max) {
				max=list[i];
				idx=i;
			}
		}
		return idx;
	}
	private static void getMargin(int maxIdx, int[] price) {//maxIdx까지 다 더하고 값 계산하고 배열 잘라서 getMargin
		if(price.length>0) {
			int pay=0;
			for(int i=0;i<maxIdx;i++) {
				pay+=price[i];
			}
			margin+=(price[maxIdx]*maxIdx)-pay;
			int [] cut=cutArray(maxIdx+1,price);
			maxIdx=getMaxIdx(cut);
			getMargin(maxIdx,cut);
		}
		
	}
}

---

-댓글보기..

수정...

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

class Solution
{
	private static long margin=0;
	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 maxPrice=-1;
			int maxPriceIdx=-1;
			int days=sc.nextInt();
			int[] price=new int[days];
			for(int i=0;i<days;i++) {
				price[i]=sc.nextInt();
				if(price[i]>maxPrice) {
					maxPrice=price[i];
					maxPriceIdx=i;
				}
			}
			getMargin(maxPriceIdx,price);
			System.out.println("#"+test_case+" "+margin);
			margin=0;
		}
	}
	private static int[] cutArray(int start, int[] original) {
		int [] cut=new int [original.length-start];
		for(int i=start;i<original.length;i++) {
			cut[i-start]=original[i];
		}
		return cut;
	}
	private static int getMaxIdx(int[] list) {
		int idx=-1;
		int max=-1;
		for(int i=0;i<list.length;i++) {
			if(list[i]>max) {
				max=list[i];
				idx=i;
			}
		}
		return idx;
	}
	private static void getMargin(int maxIdx, int[] price) {//maxIdx까지 다 더하고 값 계산하고 배열 잘라서 getMargin
		if(price.length>0) {
			int pay=0;
			for(int i=0;i<maxIdx;i++) {
				pay+=price[i];
			}
			margin+=(price[maxIdx]*maxIdx)-pay;
			int [] cut=cutArray(maxIdx+1,price);
			maxIdx=getMaxIdx(cut);
			getMargin(maxIdx,cut);
		}
		
	}
}

하하

---

문제 풀이법을 떠올리면 풀린다

풀이법을 떠올리는게 어렵다..

전에 이 비슷한 문제 풀었을때 이 방법이 떠올랐다면 풀었을텐데^^ 못풀었었네.. 지금은 풀이법이 운좋게 떠올라서 풀었고

---

-다른사람 코드 참고:https://regularmember.tistory.com/38

[SWEA] 1859. 백만 장자 프로젝트

댓글에서 다들 뒤에서부터 봐라 이러는데 뭔말인지 이해가 안가서 본 블로그

나같은경우 제일 큰값 찾고 그 앞에 부분에서 마진 계산, 제일 큰값 이후의 날들에서 그다음을로 비싼값 찾고 계산..

이런식으로 했는데

뒤에서 부터 차례로 보면 여러번 순회할 필요 없이 한번만 순회하며 마진을 구할수있다

뒤에서부터 보면서 지금 값 보다 앞의 값이 큰지 확인하고 지금 값 보다 작다면 그날은 사는날, 지금값은 파는날의 가격

그러므로 파는날의가격*여태껏확인한애들수-사는날값

보다가 더 큰수를 보게되면 파는날 가격을 새로 지정하고 앞의것을 보면서 계산

import java.util.*;
class Solution
{	
	private static long margin=0;
	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 maxPrice=-1;
			int days=sc.nextInt();
			int[] price=new int[days];
			for(int i=0;i<days;i++) {
				price[i]=sc.nextInt();
			}
			for(int i=days-1;i>=0;i--) {
				if(maxPrice<price[i]) {
					maxPrice=price[i];
				}else {
					margin+=maxPrice-price[i];
				}
			}
			System.out.println("#"+test_case+" "+margin);
			margin=0;
		}
	}
	
}