(JAVA) 백준 15903번 : 카드 합체 놀이--- [그리디]

https://www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

 

 

안녕하세요.

 

그리디 알고리즘을 활용한 문제로,

 

난이도는 쉬운 편입니다.

 

 

 

저는 처음에 간단하게 생각해서

1) 오름차순 정렬

2) 앞에서 두 장 카드 선택

3) 더해서 다시 두 장 카드 값에 대입

4) M번 1~3 반복

 

해서 맞추긴 했습니다만,

너무 효율성이 낮아서 다시 생각해봤고,

 

결국 

삽입 정렬을 활용했습니다.

 

 

알고리즘

---

간단합니다.

 

1) 처음 입력받은 카드 배열 오름차순 정렬

2) 앞에서 카드 두 장 선택

3) 숫자 더하기

4) index 1(두 번째 카드) 부터 삽입 정렬 수행

5) index 0(첫 번째 카드) 삽입 정렬 수행

6) M번동안 1 ~ 5 반복 수행

 

삽입 정렬 시 뒤의 카드 숫자가 같거나 크면 바로 정렬을 중단하기 때문에, 두 번째 카드부터 수행합니다.

 

 

 

감사합니다.

 

 

소스코드

---

 

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Arrays;
	import java.util.StringTokenizer;
	// 카드 합체 놀이
	// 그리디 알고리즘
	public class p15903 {
	static long[] cards;
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	int n = Integer.valueOf(st.nextToken());
	int m = Integer.valueOf(st.nextToken());
	st = new StringTokenizer(br.readLine());
	cards = new long[n];
	for(int i = 0; i < n; i++) {
	cards[i] = Long.valueOf(st.nextToken());
	}
	// 1. 오름차순 정렬
	Arrays.sort(cards);
	// m회 반복
	while(m --> 0) {
	// 2. 카드 두 장 더하기
	long a = cards[0];
	long b = cards[1];
	long sum = a + b;
	// 3. 대입
	cards[0] = sum;
	cards[1] = sum;
	// 4. 카드 두장 정렬
	// 삽입 정렬로 인덱스 1부터 시작
	// 1 삽입 정렬 후 인덱스 0 시작
	setInsertionSort(1);
	setInsertionSort(0);
	}
	long result = 0;
	for(long card: cards) {
	result += card;
	}
	System.out.println(result);
	}
	private static void setInsertionSort(int startIndex) {
	for(int i = startIndex + 1; i < cards.length; i++) {
	long card = cards[i - 1];
	long nextCard = cards[i];
	if(card <= nextCard) {
	break;
	}
	// swap
	cards[i - 1] = nextCard;
	cards[i] = card;
	}
	}
	}

view raw p15903.java hosted with ❤ by GitHub