BOJ 11583 - 인경호의 징검다리
https://www.acmicpc.net/problem/11583
trailling zero를 최소화 한다는 것은 그 수를 소인수분해 했을때 2와 5의 지수 중 작은 것을 최소화 하는 것과 같다. 2의 지수만을 보고 구한 것과 5의 지수만을 보고 구한 것 중 작은 값이 답이 된다. 이것은 다이나믹 프로그래밍으로 쉽게 구할 수 있다.
weighted interval scheduling
어떤 테스크가 N개 주어진다. 각 테스크는 시작시간, 종료시간, 가중치를 가지고 있다. 같은 시간에 2개 이상의 테스크를 처리할 수 없을 때 최대로 얻을 수 있는 가중치의 합을 구하라 https://www.acmicpc.net/problem/11108 https://www.acmicpc.net/problem/1666 (2차원이지만 접근법이 비슷하다고 생각함) 방법: 간단히 dp로 n^2에 풀 수 있지만 nlgn으로 줄일 수 있다. 테스크들의 시작점과 끝점을 분리하고 인덱스를 같이 저장하여 시간 순으로정렬한다. (이때 시작점인지 끝점인지 알 수 있도록 한다.) 정렬한 데이터를 선형으로 보면서 시작점일 경우 이전에 구한 최대값과 같이 계산해서 저장해 놓는다.(최대값을 바로 갱신하지 않는다.) 끝점일 경우 최대값을 갱신한다. (binary search로 현재 보는 테스크와 겹치지 않고 인덱스가 가장 큰 테스크를 찾아도 될것 같다.)
댓글
댓글 쓰기