목록구간나누기 (1)

프로그래밍에 대한 고찰 및 생각

[알고리즘][3][백준_2228][Python3] - 구간 나누기

문제이해 설명에 앞서 문제에 제시된 M(1≤M≤⌈(N/2)⌉) 에서 ⌈x⌉ 기호는 x보다 작지않은 최소 정수를 의미한다. 예를들어 N=10 M=3일때 가능한 조합들중 일부는 다음과같다. 알고리즘 전략 가장 쉽게 떠올릴수 있는 방법은 모든 경우의 수를 전부 해보는것이다. 단 일반 재귀로 작성하면 재귀호출만 해도 말그대로 2^N 만큼의 시간복잡도를 가지므로 중복호출되는 함수는 그 값을 미리 메모이제이션을 해두고 바로 값을 불러오도록 처리를 하면 될것이다. 또한 이 문제는 k번째 값을 선택할지말지 고를때 그 앞의 (k-1)개의 선택 현황에 따라 선택지가 달라질수 있다. 즉 앞의 상황과 독립적이지 않다는 것이다. 만약 앞에서 주어진 구간개수를 모두 만들었다면 k이후로는 모든 수를 선택하지 못할수도있다. 여기서 ..
알고리즘/백준 2020. 1. 15. 21:28
이전 Prev 1 Next 다음