[백준] 1049 - 기타줄 (JAVA)

1. 소요시간 : 11분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버4
4. 문제 유형 : 수학, 그리디 알고리즘
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : X
7. 문제 링크 : https://www.acmicpc.net/problem/1049
8. 푼 날짜 : 2023.03.15

1. 사용한 자료구조 & 알고리즘

그리디 알고리즘을 사용했다.

2. 풀이과정

1. 6개 패키지, 그리고 1개의 낱개 각각 어떤 값이 가장 최소 값인지 찾는다.
2. 만약 n이 6 이상이라면 6개 패키지의 가격, 그리고 6개의 낱개 *6 중 더 싼 가격으로 총합 가격에 더한다. 그리고 n을 6 감소시킨다. while문으로 이 작업을 n이 6이상인 경우 계속 진행한다.
3. while 문을 빠져나왔다면 이제 n이 5 이하인 경우를 살펴봐야 한다. 이 때에는 6개 패키지, 그리고 낱개 * n개 중 더 싼 가격으로 총합 가격에 더한다.
4. 최종적으로 총합 가격을 출력한다.

결국 그리디의 조건은 2,3 번이라고 할 수 있다.
6개 이상인 경우에는 패키지와 낱개 6을 무조건 비교.
5개 이하인 경우에는 패키지와 낱개 n 개를 비교.

그 이유는 만약 패키지의 가격이 낱개 1개의 가격보다 쌀 수도 있고 낱개 6개가 꼭 패키지 가격보다 싸다는 보장이 없는 등... 을 고려해주기 위해서이다.

3. 소스코드

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

public class Main {
	static HashSet<Integer> set=new HashSet<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();

		StringTokenizer st;

		st=new StringTokenizer(br.readLine());

		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());

		int six=Integer.MAX_VALUE;
		int one=Integer.MAX_VALUE;

		for(int i=0;i<M;i++) {
			st=new StringTokenizer(br.readLine());
			int price1=Integer.parseInt(st.nextToken());
			int price2=Integer.parseInt(st.nextToken());
			if(price1<six) 
				six=price1;
			if(price2<one) 
				one=price2;
		}
		int price=0;
		while(N>=6) {
			int min=Math.min(six,one*6);
			price+=min;
			N-=6;
		}
		
		if(N>0) {
			int min=Math.min(six,one*N);
			price+=min;
		}
		System.out.println(price);






	}

}

4. 결과

5. 회고

사실 기타줄 문제는 이전부터 몇번 봤었는데 문제가 생각보다 길다고 아 그냥 다음에 풀래 하고 넘겼었던 문제이다. 내가 풀고 싶은 문제만 풀려고 하지말자. 그리고 이 문제는 아마 한 기타줄을 1개만 사용해야 한다는 등의 조건이 있다면 더 복잡하게 풀었을 것 같다. 그렇다고 해도 그리디고 풀었을 것 같은데, 정렬을 먼저 해야한다. 하지만 패키지로 된 기타줄을 우선 정렬할지, 낱개로 된 것을 먼저 정렬할지 등... 이런 경우에는 어떻게 했어야 했을까?

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212