알고리즘 #18 : 그리디

hyeon·2022년 5월 17일
그리디알고리즘
0

알고리즘 시작

목록 보기
16/18

그리디

현재 상황에서 가장 좋은 것만 고르를 것 (탐욕법)
=> 현상황에서 가장 좋은 것만 고를 때 최적해를 구할 수있는 문제인지 확인해야함
(코테에서 그리디 문제는 그리디로 얻은해가 최적해가 되는 상황에서 이를 추론 할 수 있어야 풀리도록 출제됨)

그리디 문제들

백준 2217 : 로프

n개의 로프를 모두 사용한다면 가장 작은 로프가 들 수 있는 무게n이 가장 가장 많이 들 수 있는 무게이다.
로프를 오름차순으로 정렬한 후 가장 작은 로프n의 최대값을 구하면 된다.

import java.util.*;
public class 백준2217 {
	static int n,m,cnt=0,answer=0;
	static Scanner scan =new Scanner(System.in);
	static int MAX=Integer.MIN_VALUE;
	static StringBuilder sb=new StringBuilder();
	static String[] str;
	static int[] arr;
	public static void main(String[] args) {
		
		//출력 : 들어올릴수있는 물체의 최대 중량
		//가장 작은 로프의 *n한 값
		n=scan.nextInt();
		arr=new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=scan.nextInt();
		}
		Arrays.sort(arr);
		int a=n;
		for(int i=0;i<n;i++) {
			MAX=Math.max(arr[i]*a, MAX);
			a--;
		}
			System.out.print(MAX);
	}

}

백준 13305 : 주유소

가장 주의해야할 것은 범위에 따른 자료형이고
풀이방법을 최적화 안하면 100점을 주지않는다!

100점 코드

import java.util.*;

public class 백준13305 {
	static int n,m,cnt=0,answer=0;
	static long ans=0;
	static Scanner scan =new Scanner(System.in);
	static long MIN=Long.MAX_VALUE;
	static StringBuilder sb=new StringBuilder();
	static long[] arr;
	static long[] arr2;
	public static void main(String[] args) {
		//출력 : 최소 비용
		n=scan.nextInt();	//도시의 갯수
		arr=new long[n];
		arr2=new long[n];
		for(int i=0;i<n-1;i++) {//도로의 길이 n-1개
			arr[i]=scan.nextLong();
		}
		for(int j=0;j<n;j++) {	//주유소의 리터당 가격 
			arr2[j]=scan.nextLong();
		}
		for(int i=0;i<n;i++) {
			if (arr2[i]<MIN) {
				MIN=arr2[i];
			}
			ans+=MIN*arr[i];
		}
		System.out.print(ans);
	}

}

17점짜리 코드

`

import java.util.*;

public class Main {
	static int n,m,cnt=0,answer=0;
	static Scanner scan =new Scanner(System.in);
	static long MIN=Long.MAX_VALUE, leng;
	static StringBuilder sb=new StringBuilder();
	static String[] str;
	static long[] arr;
	static long[] arr2;
	public static void main(String[] args) {
		//출력 : 최소 비용
		n=scan.nextInt();	//도시의 갯수
		arr=new long[n];
		arr2=new long[n];
		for(int i=0;i<n-1;i++) {//도로의 길이 n-1개
			arr[i]=scan.nextLong();
			leng+=arr[i];		//도로 총길이
		}
		for(int j=0;j<n-1;j++) {	//주유소의 리터당 가격 
			arr2[j]=scan.nextLong();
		}
		long nxt=0;
		for(int i=0;i<n-1;i++) {
			MIN=Math.min(MIN,nxt+arr2[i]*leng);
			nxt+=arr[i]*arr2[i];
			leng-=arr[i];
		}
		
		System.out.print(MIN);
	}

}

58점 짜리 코드

import java.util.*;

public class Main {
	static int n,m,cnt=0,answer=0;
	static long ans=0;
	static Scanner scan =new Scanner(System.in);
	static HashMap<Integer,Integer> map=new HashMap<>();
	static double MIN=Double.MAX_VALUE;
	static StringBuilder sb=new StringBuilder();
	static String[] str;
	static long[] arr;
	static long[] arr2;
	public static void main(String[] args) {
		//출력 : 최소 비용
		n=scan.nextInt();	//도시의 갯수
		arr=new long[n];
		arr2=new long[n];
		for(int i=0;i<n-1;i++) {//도로의 길이 n-1개
			arr[i]=scan.nextLong();
		}
		for(int j=0;j<n;j++) {	//주유소의 리터당 가격 
			arr2[j]=scan.nextLong();
		}
		for(int i=0;i<n;i++) {
			if (arr2[i]<MIN) {
				MIN=arr2[i];
			}
			ans+=MIN*arr[i];
		}
		System.out.print(ans);
	}

}

백준 1758 : 알바생 강호

그냥 내림차순 정렬해주고 값구하면 되는 문제 ~ 완전 쉽다 라고 생각했는데
생각외로 시간을 많이 잡아먹었다

이유

  1. comprator의 type이 primitive type은 안되고 wrapper class만 가능했다는 사실
    지금까지 푼 정렬문제는 이차원 배열이거나 string이여서 몰랐다ㅠㅠ
  2. 편의를 위해서 인덱스를 1부터 시작하려고 했으나 그러면 index 0이 비어있으므로 sort가 되지않고 널포인터에러가 뜬다. 다시 0부터 시작하는 걸로 바꿨다.

참고로 자료형도 주의해야한다. 범위가 int를 넘을 것같다.

import java.util.*;

public class 백준1758 {
	static int n,m,cnt=0,answer=0;
	static long ans=0;
	static Scanner scan =new Scanner(System.in);
	static long MIN=Long.MAX_VALUE;
	static StringBuilder sb=new StringBuilder();
	static Integer[] arr;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		n=scan.nextInt();	//사람의 수
		arr=new Integer[n];
		for(int i=0;i<n;i++) {
			arr[i]=scan.nextInt();
		}
		Arrays.sort(arr,Comparator.reverseOrder());

		for(int i=0;i<n;i++) {
			long tip= arr[i]-(i);
			if(tip<0) {
				tip=0;
			}
			ans+=tip;
		}
		System.out.print(ans);
	}


}

백준 11508 : 2+1 세일

풀이방법은 윗문제와 같다

import java.util.*;

public class 백준11508 {
	static int n,m,cnt=0,answer=0;
	static long ans=0;
	static Scanner scan =new Scanner(System.in);
	static long MIN=Long.MAX_VALUE;
	static StringBuilder sb=new StringBuilder();
	static Integer[] arr;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		n=scan.nextInt();
		arr=new Integer[n];
		for(int i=0;i<n;i++) {
			arr[i]=scan.nextInt();
		}
		Arrays.sort(arr,Comparator.reverseOrder());
		for(int i=0;i<n;) {
			if(n-i<3) {
				ans+=arr[i];
				i++;
			}
			else {
				ans+=arr[i]+arr[i+1];
				i+=3;
			}
		}
		System.out.print(ans);
		
	}

}

백준11399 ATM

풀이는 위와 같다 문제가 다 비슷비슷 하구나~

import java.util.*;

public class 백준11399 {
	static int n,m,cnt=0,answer=0;
	static long ans=0;
	static Scanner scan =new Scanner(System.in);
	static long MIN=Long.MAX_VALUE;
	static StringBuilder sb=new StringBuilder();
	static Integer[] arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		n=scan.nextInt();
		arr=new Integer[n];
		for(int i=0;i<n;i++) {
			arr[i]=scan.nextInt();
		}
		Arrays.sort(arr);
		int a=n;
		for(int i=0;i<n;i++) {
			ans+=arr[i]*a;
			a--;
		}
		System.out.print(ans);
		
	}

}

백준 20115: 에너지 드링크

/2를 하는 과정에서 소수점이 나올수도 있기때문에 double 형을 써주었다
풀이는 위와같습니다

import java.util.*;
public class 백준20115 {
	static int n,m,cnt=0,answer=0;
	static double ans=0;
	static Scanner scan =new Scanner(System.in);
	static long MIN=Long.MAX_VALUE;
	static StringBuilder sb=new StringBuilder();
	static Integer[] arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		n=scan.nextInt();
		arr=new Integer[n];
		for(int i=0;i<n;i++) {
			arr[i]=scan.nextInt();
		}
		Arrays.sort(arr);
		for(int i=0;i<n;i++) {
			if(i==n-1) {
				ans+=arr[i];
			}
			else ans+=(double)arr[i]/2;
		}
		System.out.print(ans);
	}

}

백준 1541: 잃어버린 괄호

import java.util.*;

public class 백준1541 {
	static int i,n,m,cnt=0,answer=0;
	static int ans=0;
	static Scanner scan =new Scanner(System.in);
	static long MIN=Long.MAX_VALUE;
	static StringBuilder sb=new StringBuilder();
	static int[] arr;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str=scan.next();
		int leng=str.length();
		for(;i<leng;) {
			if(i==0) {
				ans+=cal(str);
			}
			else {
			if(str.charAt(i)=='-') {
				i++;
				while(i<leng) {
					if(str.charAt(i)=='-') {
						i++; 
						break;
					}
					
					ans-=cal(str);
					i++;
				}
			}
			else {
				i++;
				ans+=cal(str);
			}
			}
			
		}
		System.out.print(ans);
		
	}
	static int cal(String str) {
		String num="";
		while(i<str.length()&&str.charAt(i)!='-'&&str.charAt(i)!='+') {// 부호 나올 때까지
			
			num+=str.charAt(i);
			i++;
		}
		return Integer.parseInt(num);
	}

}

백준 16953 :A->B

아이디어만 도출해내면 쉬운문제라고 생각하고 금방 풀었지만 47%에서 계속 시간초과가 났다. 오랫동안 47%에서 머물러있어서 무한루프에 걸린게 아닐까 생각했는데 아니나다를까 while문의 ans!=a조건이나 내부의 if문의 조건 모두 만족하지않는 반례가 있었다. 만약 ans가 3이고 a가 2라면 아무조건에도 만족하지않으므로 무한루프에 빠지게 되는것! 그래서 else문으로 예외처리를 해주었다.

import java.util.Scanner;

public class 백준16953 {
	static long a,b,cnt=0,answer=0;
	static long ans=0;
	static Scanner scan =new Scanner(System.in);
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		a=scan.nextLong();
		b=scan.nextLong();
		if(b%2!=0&&b%10!=1) { //2로 나누어 떨어지지 않고 1로 끝나지도 않는 수이면
			System.out.print(-1);
			System.exit(0);
		}
		else {
			ans=b;
			while(ans!=a) {
				 if(ans<a) {
						System.out.print(-1);
						System.exit(0);
					}
				if(ans%10==1&&ans!=1) {	//1로 끝나는 수이면
					ans=(ans-1)/10;
					cnt++;
				}
				else if(ans%2==0) {
					ans=ans/2;
					cnt++;
				}
				else {
					System.out.print(-1);
					System.exit(0);
				}
				
			}
		}
		System.out.print(cnt+1);
	}

}
profile
hyeon
남기고 싶은 개발자입니다 :>
이전 포스트

알고리즘 #17 : 분할정복

다음 포스트

알고리즘 #19 : 최단 경로

0개의 댓글