문제
DDR을 하는데, 에너지를 최소한으로 쓰고 게임을 끝내는 방법에 대한 단순한 문제이다.
재정의
greedy 한가? (탐욕적 선택 속성을 가지는가?)
앞선 선택이 뒤의 선택에 영향을 미치지 않는다면, greedy하게 풀 수 있을 것이다.
현재의 발을 옮겼다가, 뒤 이어 이전 발의 위치만 무한으로 나온다면 손해를 보게 된다. -> greedy하게 풀 수 없다.
완전 탐색
결국 모든 경우의 수를 확인해야 하므로, 완전 탐색을 사용한다.
브루트 포스를 생각없이 하면 (2 ^ 10,000)이 되어 버린다.
그럼 상태 공간을 고려를 해 보자.
상태 공간 분석 및 정의
게임의 길이가 3이고 각 상태를 A, B, C라고 하자.
각 상태에서는 1 ~ 5의 값을 가질 수 있다고 하자.
그럼 A가 1이고, C가 5로 끝난다고 할 때, 가능한 경우의 수는 많다.
A | B | C |
1 | 1 | 5 |
1 | 2 | 5 |
1 | 3 | 5 |
1 | 4 | 5 |
1 | 5 | 5 |
하지만 우리는 과정따위 궁금하지 않고, 최소 비용만 궁금하다.
그래서 A, B, C로 표현하지 않고 A -> C로 표현하는 것이 효율이 좋다.
이를 식으로 만들어 보면,
Solve(idx: int, foot: tuple[int]) -> int
idx부터 게임을 진행하고, 발 상태가 foot일 때 드는 최소 비용.
상태 공간은 command의 index와 왼발과 오른발의 상태 3개로 정의가 된다.
그러면, 상태 공간의 중복이 많이 일어나는 것은 자명 하므로, DP를 사용한다.
풀이
선택지는 왼발또는 오른발을 움직이는 것이다.
1. 왼발 움직이기 + 왼발을 움직였을 때, 그 이후의 최소비용
2. 오른발 움직이기 + 오른발을 움직였을 때, 그 이후의 최소 비용
위에서 1, 2 중에 더 적은 비용을 선택하고 이 값을 재사용하는 방식으로
Memorization을 하면 풀리는 간단한 문제이다.
def solve(idx: int, foot: tuple[int]) -> int:
if cmds[idx] == 0:
return 0
if (ret := cache.get((idx, foot))):
return ret
ret = move_cost(foot[0], cmds[idx]) + solve(idx+1, (cmds[idx], foot[1]))
ret = min(ret,
move_cost(foot[1], cmds[idx]) + solve(idx+1, (foot[0], cmds[idx])))
cache[(idx, foot)] = ret
return ret
'알고리즘' 카테고리의 다른 글
좌표 2배로 관리하기 (0) | 2024.02.21 |
---|---|
Leaf_node 세는 방법 (0) | 2024.02.18 |
최단 경로 관리하기 (0) | 2024.01.27 |
DP를 정의 하는 방법 (0) | 2024.01.25 |
UnionFind와 순서 강제로 탐색하기 (0) | 2024.01.24 |