문제 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 재정의 3월 1일부터 11월 30일까지를 커버하는 최소의 꽃 개수 구하기. 1. x월 y일을 비교할 수 있게 정량화 하기. 2. 늦게 끝나는 순, 일찍 시작하는 순으로 정렬하기 (상위 호환 처리를 위해) 3. 정렬된 꽃을 11월 30일이 될 때 까지, 하나씩 집기. 월과 일을 정량화 하는 방법은 무수히 많지만, 두 가지 형태를 주로 사용한다. 날짜 비교하기 이 글에서 설명 된 방식 중, Day로 표현하는 방식을 사용 한다. 탐색의 중복 ..
문제 & 재정의 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 이전의, 인덱스로 상태관리하기 글의 문제와 동일하다. Tabulation으로 DP Tabulation으로 DP를 하게 되면, 상태 공간을 적층식으로 만들어 가게 된다. 즉, 현재 상태공간이 어느 상태공간에서 전이 됐는지 로직상에서 확인이 된다. 이는 적층식으로 전이 되는 과정에서, Path도 전이시켜 따로 관리하면 단순하게 해결할 수 있다. dp = [[0] * (n+2) for _ in range(m+2)] path = [[0] * (n+2) for _..
문제 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 재정의 두 가지 제약 조건이 존재한다. 정해진 투자액수만큼 투자 한다. 한 기업에는 한 번만 투자할 수 있다. 금액의 조합을 정해야 하고, 기업의 조합도 정해야 한다. 완전 탐색을 활용한다. 비 효율적인 상태공간 정의 완전 탐색을 해야하는 문제이다. 상태 공간을 기업의 개수, 남은 금액으로 단순하게 정의 했다. 그렇게 되면 다음과 같이 코드가 구성 된다. 다음 코드의 문제점이 무엇인지 생각 해 보자... def get_max_profit() -> List[int]:..
