문제 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net DDR을 하는데, 에너지를 최소한으로 쓰고 게임을 끝내는 방법에 대한 단순한 문제이다. 재정의 greedy 한가? (탐욕적 선택 속성을 가지는가?) 앞선 선택이 뒤의 선택에 영향을 미치지 않는다면, greedy하게 풀 수 있을 것이다. 현재의 발을 옮겼다가, 뒤 이어 이전 발의 위치만 무한으로 나온다면 손해를 보게 된다. -> greedy하게 풀 수 없다. 완전 탐색 결국 모든 경우의 수를 확인해야 하므로, 완전 탐색을 사..
문제 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 재정의 경우의 수를 활용하여 풀려고 하니 쉽지 않았다. 단순 곱사건(동시에 일어나는 사건)이 아니라, 합사건도 같이 일어나기 때문이다. 이는 완전 탐색을 요구하고, 상태 공간의 중복이 발생한다. 그냥 DP를 사용하려고 하니, 상태 공간의 정의가 마음에 들지 않았다. 손으로 작성 해 보니 어떤 상태 공간을 사용할지 찾을 수 있었다. 역시 DP각은 손으로 써서 봐야 잘 보인다. 재귀 함수로 문제 정의하기 완전 탐색을 해야함을 인지 했으니, 일단 재귀 함수로 간단하게 정의를..
문제 & 재정의 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 이전의, 인덱스로 상태관리하기 글의 문제와 동일하다. Tabulation으로 DP Tabulation으로 DP를 하게 되면, 상태 공간을 적층식으로 만들어 가게 된다. 즉, 현재 상태공간이 어느 상태공간에서 전이 됐는지 로직상에서 확인이 된다. 이는 적층식으로 전이 되는 과정에서, Path도 전이시켜 따로 관리하면 단순하게 해결할 수 있다. dp = [[0] * (n+2) for _ in range(m+2)] path = [[0] * (n+2) for _..
