SW 1859. 백만 장자 프로젝트

SW Expert Academy

SW Expert Academy

후 D1까지는 완전 식은 죽 먹기였는데 뭐냐 ? D2들어오자마자 갑자기 난이도 확 어려워졌따..

결국 풀긴 풀었는데 시간초과가 나왔다.

 

package algorithm;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
public class Solution
{
	public static void main(String args[]) throws Exception
	{
		/*
		   아래의 메소드 호출은 앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
		   여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
		   이 코드를 프로그램의 처음 부분에 추가하면 이후 입력을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
		   따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 메소드를 사용하셔도 좋습니다.
		   단, 채점을 위해 코드를 제출하실 때에는 반드시 이 메소드를 지우거나 주석 처리 하셔야 합니다.
		 */
		//System.setIn(new FileInputStream("C:\\so_Project\\workspace\\BaekJoon\\src\\algorithm\\input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		List <int[]>price = new ArrayList<>();
		
		for(int i=0;i<num;i++) {
			int date = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			int arr[] = new int[date];
			
			for(int j=0;j<date;j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}
			price.add(arr);
		}
		for(int i=0;i<price.size();i++) {//각 테스트 케이스마다 반복
			int result = 0;
			int sum=0;
			int ch = 0;
			for(int k=1;k<price.get(i).length;k++) { //한 케이스 안의 모든 요소들을 검사
				sum =0;
				int temp = price.get(i)[k];
				for(int j=0;j<k;j++) { //temp의 앞 부분까지 반복
					if(price.get(i)[j] < temp) { //앞 부분의 요소값이 temp보다 작다면
						sum +=(temp-price.get(i)[j]);
					}
					else if(price.get(i)[j]==temp) {//앞 부분의 요소값이 temp랑 같으면
						continue;
					}
					else {//앞 부분의 요소값이 temp보다 크다면
						sum = 0;
						ch =1;
					}
				}
				result+=sum;
			}
			if(ch==0)
				System.out.println("#"+(i+1)+" "+sum);
			else
				System.out.println("#"+(i+1)+" "+result);
		}
	}
}

 

흠 첨부터 다시 생각해서 다시 풀었지만 위 코드랑 비슷했다.

package algorithm;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
public class Solution
{
	public static void main(String args[]) throws Exception
	{
		/*
		   아래의 메소드 호출은 앞으로 표준 입력(키보드) 대신 input.txt 파일로부터 읽어오겠다는 의미의 코드입니다.
		   여러분이 작성한 코드를 테스트 할 때, 편의를 위해서 input.txt에 입력을 저장한 후,
		   이 코드를 프로그램의 처음 부분에 추가하면 이후 입력을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
		   따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 메소드를 사용하셔도 좋습니다.
		   단, 채점을 위해 코드를 제출하실 때에는 반드시 이 메소드를 지우거나 주석 처리 하셔야 합니다.
		 */
		//System.setIn(new FileInputStream("C:\\so_Project\\workspace\\BaekJoon\\src\\algorithm\\input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		List <int[]>price = new ArrayList<>();
		
		for(int i=0;i<num;i++) {
			int date = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
			int arr[] = new int[date];
			
			for(int j=0;j<date;j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}
			price.add(arr);
		}
		List <Integer>count = new ArrayList<>();
		for(int i=0;i<price.size();i++) {//각 테스트 케이스마다 반복
			int sum =0;
			int result = 0;
			int max = 0;
			boolean ch = false;
			for(int j=1;j<price.get(i).length;j++) {//한 테스트 케이스 내에서 케이스의 갯수만큼반복
				int temp = price.get(i)[j];
				result+=sum;
				sum=0;
				for(int k=0;k<j;k++) { //현재 temp 직전까지 반복
					if(temp > price.get(i)[k]) { //현재 수가 이전 요소보다 클 때
						sum += (temp-price.get(i)[k]); //sum에 차이값 더해가기
					}
					else if(temp == price.get(i)[k]) { //현재수랑 이전 요소가 같을 때
						continue;
					}
					else { //현재수가 이전 요소보다 작을 때
						sum= 0 ;
						ch=true;
					}
					if(max<sum)
						max = sum;
				}
			}
			if(ch==true) { //제일 큰 수가 중간중간에 섞여있을 때
				System.out.println("#"+(i+1)+" "+(result+sum));
			}
			else //제일 큰 수가 제일 뒤에 있을 때
				System.out.println("#"+(i+1)+" "+max);
		}
	}
}

그리고 역시 제한시간 초과가 나왔따.

 

다른 코드들을 찾아봤는데 뒤에서부터 맨 뒷 수가 제일 큰 수라고 생각하고 풀어야한다고 한다.

 

package algorithm;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/*
   사용하는 클래스명이 Solution 이어야 하므로, 가급적 Solution.java 를 사용할 것을 권장합니다.
   이러한 상황에서도 동일하게 java Solution 명령으로 프로그램을 수행해볼 수 있습니다.
 */
public class Solution
{
	public static void main(String args[]) throws Exception
	{
		//System.setIn(new FileInputStream("C:\\so_Project\\workspace\\BaekJoon\\src\\algorithm\\input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = Integer.parseInt(br.readLine());
		
		for(int i=1;i<=num;i++) {
			int data = Integer.parseInt(br.readLine());
			int arr[] = new int[data];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<data;j++) 
				arr[j] = Integer.parseInt(st.nextToken());
			
			int result = 0;
			int max = arr[data-1]; //맨 뒤에수를 max라고 가정.
			
			for(int k=data-2;k>=0;k--) {
				if(arr[k]>max) {
					max = arr[k]; //자기보다 큰 수 만나면 max변경
				}
				else { //자기보다 작거나 같으면
					result += (max-arr[k]);
				}
			}
			System.out.println("#"+i+" "+result);
		}
	}
}

여기서 result의 자료형을 long으로 안 해줬더니 틀렸다

그 이유는 ? 자료가 1,000,000개까지 있을 수 있는데

각 날의 매매가는 10,000 이하이고 1,000,000개의 자료가 하나빼고 싹다 1원이었다면 하나에 9999의 이득이니까 20억을 훠얼씬 넘는다 !

 

끄읏..~