알고리즘
[BOJ] Dance Dance Revolution - 2342
🎨 문제 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 📘 풀이 DP와 분할정복을 혼합하여 풀었습니다. 완전 탐색의 경우 왼발과 오른발을 쓰는 지(두가지)와 입력 수열의 길이가 100,000이 최대이므로 시간 복잡도가 2의 100,000제곱으로 TLE가 발생합니다. DP 배열 DP = int[눌러야하는 발판][왼발 위치][오른발 위치] 눌러야할 발판은 입력받은 배열의 길이입니다. 마지막 발판은 0이므로 1을 빼주어도 됩니다. 발의 위치는 다섯가지로 중앙, 위, 아래, 왼쪽,..
