KwanIk Devlog
[ 백준 1715번 ] 카드 정렬하기
Algorithm/문제풀이 2023. 3. 10. 16:35

1. 문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 입력으로 제공된 카드들의 누적합을 최소로 만드는 경우의 수를 만들라는 문제다. 이는 Greedy로 접근이 가능한데 이유는 아래와 같다. a, b, c, d 총 네 개의 카드 묶음(a < b < c < d)이 있다고 가정해보자. 이 때, 먼저 만든 묶음은 또 다른 카드 묶음과 합쳐져야 하므로 한 번 더 더해져야 함을 의미한다. 즉, 더 큰 카드 묶음을 이용하여 새로운 묶음을 만들수록 큰 수가 중복해서 더해진다는 것을 의미한다. ..

반응형