훔쳐야 할 m개에서 적어도 하나씩을 포함해야 하니까 m-n개를 서로가 나눠갖아야 한다 일단 생각나는 것이 브루트포스라서 브루트포스로 해결했는데, 더 쉽고 빠른 알고리즘이 존재하는 것 같다 [추가] 19.06.06 중복조합으로 풀 수 있다. nH(m-n)으로 계산할 수 있다 문제: https://www.acmicpc.net/problem/17213 https://github.com/surinoel/boj/blob/master/17213.cpp https://github.com/surinoel/boj/blob/master/17213.c

트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. [출처] https://www.acmicpc.net/problem/1967 [원리] https://blog.myungwoo.kr/112 https://github.com/surinoel/boj/blob/master/1967.cpp

처음에는 재귀함수로 3^N

N 제한을 봤을 땐 O(N)에 해결해야 하는 문제다. 각 위치에서 최댓값만 알면 된다. 기준을 나눴을 때 left에서의 최댓값 sleft, 오른쪽에서의 최댓값 sright 배열에 최댓값만을 넣을 수 있다. sleft는 왼쪽부터 탐색을 진행하면서 최댓값을 교체해가면서, 반대로 sright는 오른쪽부터 탐색을 진행하면서 최댓값을 교체할 수 있다. 그리고 채워진 배열을 비교하면 시간복잡도 O(N)으로 해결할 수 있다 문제: https://www.acmicpc.net/problem/17251 https://github.com/surinoel/boj/blob/master/17251.cpp

데이터를 하나씩 체크한다면 시간복잡도는 O(N) = 10000000*1000*1000으로 매우 큰 수이다. 하지만 높이가 저장된 배열을 잘 이용하면 이 문제를 해결할 수 있다. 즉 천만번을 탐색해야만 시간 안에 끝낼 수 있다 각 높이마다 배열에 저장하고, 가장 높은 곳에서 아래로 내려가면서 해당 높이는 제외하면서 밑 층을 덮으면서 내려가면 된다. 문제: https://www.acmicpc.net/problem/17245 https://github.com/surinoel/boj/blob/master/17245.c

서로 다른 n개에서 k개를 순서와 관계없이 뽑는 조합 공식은 다음과 같다 프로그래밍도 위의 식에 맞춰서 계산할 수 있다 문제: https://www.acmicpc.net/problem/11050 https://github.com/surinoel/boj/blob/master/11050.cpp