그건 장난감이 아니라 돌이야

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net "Dance Dance Revolution" 일명 DDR을 플레이할 때, 왼발과 오른발의 위치에 따라 다음 버튼을 누르는데 소비하는 에너지가 다르다면 눌러야하는 버튼이 순서대로 주어졌을 때, 가장 적은 에너지로 버튼을 누를 수 있는 에너지를 구하는 문제이다. 일단 비슷한 문제가 하나 생각나는데 [2618번]경찰차 문제가 생각난다. 하지만 이 문제가 더 단순화된 버..

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제를 핵심만 남겨서 해석해보자면 다음과 같다. "정렬되지 않은 정수 배열이 주어질 때 연속적으로 증가하는 가장 큰 정수 배열의 길이를 구하여라" 이는 흔히 LIS (Longest Increasing Subsequence), 즉 최장 증가 부분 수열이라 불리는 문제이다. 다음과 같은 논리로 위와 같은 문제를 DP로 풀 수 있다. 먼저, DP 배열은 다음과 같이 선언한다. DP[지금 탐색 중인 상자의 번호]..