문제 출처 : https://www.acmicpc.net/problem/11066 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ) 해설합쳐야 하는 파일을 두 수열로 나눌 수 있다. 최적으로 합쳐야 하는 구간을 i ~ j 라고 할 때 임의의 k에 대해 ( i 0 ? mem[i - 1] : 0); } int main() { int t; scanf("%d", &t); for (; t--; ) { int i, j, n; memset(dp, -1, sizeof dp); scanf("%d", &n); for (i = 0; i 0 ? mem[i - 1] : 0); } printf("%d\..
문제 출처 : https://www.acmicpc.net/problem/1715 문제 해결에 필요한 알고리즘 : 그리디 알고리즘 해설 가장 작은 두 수끼리 계속 합쳐주는 것이 가장 최적이다. priority queue를 이용하여 문제를 해결 할 수 있다. 모든 수를 큐에 삽입한 후 가장 작은 두 수를 꺼내 연산한 뒤 결과를 다시 큐에 넣어주면 된다. 이렇게 큐에 한가지의 숫자가 남을 때 까지 하면 최소로 비교하는 횟수를 알 수 있다. 정당성 증명 S(A, b)를 A라는 수의 집합과 b라는 수를 포함하는 카드의 집합이라고 정의한다. MIN(S) 는 수의 집합에서 가장 최적으로 비교하는 횟수라고 정의한다. S(A, b), S(A, c)가 있을 때 b > c 라고 하면, MIN(S(A, b)) > MIN(S(..
문제 출처 : https://www.acmicpc.net/problem/11652 문제 해결에 필요한 알고리즘 : map자료구조를 이용한 단순 구현문제 해설주의해야 할 점 : 범위가 ~ 이므로 C/C++ 기준 long long을 사용해야 풀 수 있음. 이 문제는 서로 다른 카드 중 가장 많은 카드를 찾는 문제이다. 범위가 작다면 카드를 배열의 인덱스로 이용해 갯수를 셀 수 있지만 범위가 크므로 배열은 사용이 불가하다. 그래서 map자료구조를 이용하면 된다. map자료구조를 이용해 데이터를 삽입하면서 갯수를 체크해준다. 이때마다 조건에 맞는 카드를 선택하면 된다. 다른 방법으로 정렬을 한뒤 순회하며 연결되어있는 갯수를 세 업데이트 하는 방법도 존재한다. 시간복잡도map에 삽입을 하는데 만큼의 시간이 걸리고..