(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 반복 수행

 

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

 

 

 

감사합니다.

 

 

소스코드

---