백준 알고리즘 그리디

11047. 동전 0

 

그리디의 기초문제.

 

import java.util.Arrays;
import java.util.Scanner;

class main {
	public static void main(String[] args)  {
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
	    int money=sc.nextInt();
	    int arr[]=new int[n];
	    int mok=0,nam=0;
	    int sum=0;
	    
	    for(int i=0;i<n;i++) {
	    	int x=sc.nextInt();
	    	arr[i]=x;
	    }
	    Arrays.sort(arr);
	    
		for(int i=n-1;i>=0;i--){ 
			 if(money>=arr[i]) {
				 mok=money/arr[i];
				 nam=money%arr[i];
				 money=nam; 
				 sum=sum+mok; 
			 } 
		 } System.out.println(sum);
		
	}}

 

 

 

 

 

 

1931. 회의실 배정

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class main {
	public static void main(String[] args)  {
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
	    int arr[][]=new int [n][2];
	    int count=0;
	    int end=-1;
	    
	    for(int i=0;i<n;i++) {
	    	arr[i][0]=sc.nextInt();
	    	arr[i][1]=sc.nextInt();
	    }
	    Arrays.sort(arr, new Comparator<int[]>() {
	        @Override
	        public int compare(int[] o1, int[] o2) {       
	        	if(o1[1]==o2[1]) {                               //[x][y] y(1)인덱스 값 비교 
	        		return Integer.compare(o1[0],o2[0]);         //같다면 x(0) 비교
	        	}
	        	return Integer.compare(o1[1],o2[1]) ;
	        }
	    });
	    for(int i=0;i<n;i++) {
	    	if(arr[i][0]>=end) {          // 시작이 엔드보다 크다면 다음거 가능
	    		end=arr[i][1];         
	    		count++;
	    		
	    	}
	    }
	    System.out.println(count);
	}}

2차원 배열 정렬에서 오래걸림..

배우게 된 코드! 

2차원 배열 ex. arr[x][2] -> arr[][2] 기준으로 정렬 ->첫번째 실행 ->그 다음 arr[x][0] 의 값이 전의 end보다 작다면 패스

 

 

 

--------------------------------------2020/10/20------------------------------------

 

11399. ATM

 

import java.util.Arrays;
import java.util.Scanner;

class main {
	public static void main(String[] args)  {
		
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
	    int arr[]=new int [n];
	    int time=0;
	    int totaltime=0;
	    
		for(int i=0;i<n;i++) {
			int s=sc.nextInt();
			arr[i]=s;		
		}
		Arrays.sort(arr);
		
		for(int i=0;i<n;i++) {
			time=time+arr[i];
			totaltime=totaltime+time;
		}
		System.out.println(totaltime);
	}}

생각보다 어렵지 않았던 문제! 정렬후 각 시간에 대한 값 더해주면 됨