DP

문제 링크 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 🏷️ 카테고리 # 다이나믹 프로그래밍 ⏳ 시간복잡도 📒 해설 오락실에 있는 DDR 게임을 할 때 버튼을 어떤 발로 밟을 때, 가장 적은 힘이 드는지를 구하는 문제입니다. N이 작다면 완전 탐색을 통해 풀 수도 있지 않을까 싶지만, N이 10만이기 때문에, 이용할 수 없는 문제였습니다. 상태 공간 트리를 그린다면, 중복되는 구간이 많이 나오기 때문에, 그림을 그려본다면 빠르게 DP 문제라는 것을 알 수 있었습니다. 📜 ..