====== Dance Dance Revolution ====== ===== 풀이 ===== * 기초적인 DP 문제 * DP[n][(x,y)] 를 두 발의 위치가 x와 y인 상태로 n번째지시사항까지 처리했을때의 최소 힘이라고 정의하고, energy(a, b)를 a에 있던 발을 b로 옮길때 드는 힘이라고 정의하자. n번째 지시사항이 x였다면 점화식은 다음의 형태로 나온다 * DP[n][(x,y)] = min_z{DP[n-1][(z,y)]+energy(z,x)} * 불가능한 포지션, x가 포함되지 않은 포지션 또는 두 발이 같은 위치에 있는 포지션들은 DP값을 전부 INF로 만들어주면 된다. * 그러나 n번째 지시사항이 끝난 뒤에는 한 발은 항상 특정 위치에 가있어야 하기 때문에, 이렇게 모든(x,y)에 대해서 테이블을 유지하는 것은 조금 비효율적이다. DP테이블을 조금 수정해서, DP[n][y] 를 한발의 위치는 n번째 지시위치에, 다른 발의 위치는 y에 가있는 경우의 최소 힘으로 정의해보자. n번째 지시위치를 cmd[n]이라고 하면, n-1번째에서 발이 cmd[n-1]과 x에 있었으므로, n번째에는 x에 있던 발로 cmd[n]을 누르는 경우와 cmd[n-1]에 있던 발로 cmd[n]을 누르는 두가지로 나눠서 생각할수 있다. 즉 점화식은 아래처럼 나온다 * DP[n][x] = min{DP[n-1][x]+energy(cmd[n-1],cmd[n]), DP[n-1][cmd[n]]+energy(cmd[n-1],x)} * 위의 방식에 비해서 메모리와 속도 모두 조금 더 효율적이다. * 어떤 방식으로 DP식을 정의하든, 포지션의 갯수는 고정되어 있으므로 상수라고 놓으면 시간복잡도는 O(n)이다. (n=지시사항의 갯수) ===== 코드 ===== """Solution code for "BOJ 2342. Dance Dance Revolution". - Problem link: https://www.acmicpc.net/problem/2342 - Solution link: http://www.teferi.net/ps/problems/boj/2342 Tags: [DP] """ INF = float('inf') def energy(cur_pos, next_pos): if cur_pos == next_pos: return 1 if cur_pos == 0: return 2 elif abs(cur_pos - next_pos) == 2: return 4 else: return 3 def main(): positions = [int(x) for x in input().split()] positions.pop() dp_cur = [INF] * 5 dp_cur[0] = energy(0, positions[0]) for prev_pos, cur_pos in zip(positions, positions[1:]): dp_prev = dp_cur # (prev_pos, pprev_pos) -> (cur_pos, pprev_pos) energy_from_prev = energy(prev_pos, cur_pos) dp_cur = [tot_energy + energy_from_prev for tot_energy in dp_prev] dp_cur[cur_pos] = INF # (prev_pos, pprev_pos) -> (prev_pos, cur_pos) if prev_pos != cur_pos: dp_cur[prev_pos] = min( tot_energy + energy(pprev_pos, cur_pos) for pprev_pos, tot_energy in enumerate(dp_prev)) print(min(dp_cur)) if __name__ == '__main__': main() {{tag>BOJ ps:problems:boj:골드_3}}