https://www.acmicpc.net/problem/1626 두 번째로 작은 스패닝 트리 방향성이 없는 그래프 G가 있고 이 그래프에서의 최소 스패닝 트리 T가 존재한다. 문제는 최소 스패닝 트리 T보다는 크면서 가장 작은 스패닝 트리인 'The second minimum spanning tree'를 구하는 것이다.MST와 second MST의 모습입력첫째 줄에 그래프의 정점 수 V(1 ≤ V ≤ 50,000)와 에지 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 에지로 연결된 두 정점과 그 에지의 가중치가 주어진다. 음수 가중치는 없으며, 답은 int 범위를 넘지 않는다.출력두 번째로 작은 스패닝 트리의 값을 출력한다. 만약 스패닝 트리나 두 번재로 작은 스패..

https://www.acmicpc.net/problem/6591 정답이 int범위 안에 들어온다는 힌트가 주어진 Combination을 구하는 문제이다. 파스칼의 삼각형을이용한 DP로 접근을 하면 n = k = 2^(31)-1 인 경우도 있기 때문에 배열자체를 잡을 메모리가 부족하다. (DP배열을 벡터로 짜보면 될것같기도한데.. 해보진않음) 간단하게 정말 조합을 구하는 손으로 구하는것처럼 계산하면 overflow없이 계산할 수 있다. 먼저 r>n/2인경우에 r=n-r로 바꿔준다. (∵ nCr = nC(n-r)) r>0인 경우만 생각해보면, n/2>=r 이고, r>0므로 (n-r+1) >= (r+1)/r > 1 을 만족한다. 따라서 (n-r+1)/r > 1 이고, nCr < 2^31 이므로 nC(r-1)..

https://www.acmicpc.net/problem/14432 (머그컵 E번) 이 문제의 핵심은 문제 마지막문단에 있는 "(단, 임의의 마을 A에서 B까지 무조건 한 가지 경로가 존재한다.)" 이다. 다시말해 이 마을들간의 관계는 트리형태이고, 따라서 한점을잡아 root로 간주하여 DFS로 탐색하면서 값을 갱신해주면 정답을 도출해 낼 수 있다.

https://www.acmicpc.net/problem/14437 (머그컵 A번) DP로 접근하면 D[현재위치][남은횟수]를 가지고 풀이하면 O(N*S)에 풀 수 있을 것 처럼 보인다. 다른 방법으로는 중복조합과 포함배재의 원리를 이용해서 풀 수도 있다. 중복조합을 이용하면 속도도 빠를 뿐 아니라, combination 값을 구할 때 DP가 아닌 fermat little thm이용해서 풀면 배열을 잡을 필요가 없어진다. 즉 메모리에 구애받지 않는 풀이가 된다. 시간복잡도는 O(N+logP).