[C++] BOJ 2342 - Dance Dance Revolution

BOJ 2342 - Dance Dance Revolution (https://www.acmicpc.net/problem/2342)

 

01. 🔎 문제 탐색

1. { 0: 중심, 1: 위, 2: 왼쪽, 3: 아래, 4: 오른쪽 }
2. 한 번에 한 발만 움직여야 함
3. 게임 시작을 제외하고 두 발이 같은 지점에 있으면 안 됨
4. 중앙에서 다른 지점으로 움직이면 2만큼의 힘 사용 (0 -> 1,2,3,4)
5. 중앙이 아닌 한 지점에서 인접한 지점으로 움직이면 3만큼의 힘 사용 (Ex. 1 -> 2, 4)
6. 중앙이 아닌 한 지점에서 반대편으로 움직이면 4만큼의 힘 사용 (Ex. 1 -> 3)
7. 같은 지점으로 움직이면 1만큼의 힘 사용 (Ex. 1 -> 1)

 
* 다음 발판의 지시사항이 수열로 주어졌을 때, 모든 지시사항을 만족하는 최소 힘을 구해야 함
 
 

01-1. 가능한 시간 복잡도

• 시간 제한 2초로 시간복잡도가 O(N^2) 이하가 되도록 구현할 수 있음

01-2. 알고리즘 선택

• 그리디 알고리즘을 통해 항상 최소의 힘을 사용하도록 고를 경우, 상황에 따라 최적의 수가 나오지 않을 가능성이 있음
  • 지금 당장은 최소일지라도 발의 상태 (양 발이 각각 반대편에 있는 경우 Ex, (1, 3))에 따라 결과가 달라질 수 있기 때문
• 따라서, 모든 경우의 수를 탐색하되, 중복된 연산을 피하기 위해 단계와 발(좌/우)에 따른 최소 힘을 메모이제이션

02. 📝 코드 설계하기

• 각 지점에서 이동했을 때, 발생하는 가중치는 5 * 5 개로 테이블을 생성
• 존재할 수 없는 경우의 수에는 큰 수를 더해줘 최적의 수에서 배제

1. 지시사항을 배열로 입력받음
2. 재귀함수로 인자(현재단계, 오른발 위치, 왼발 위치)를 전달
   1. 마지막 단계 (0) 일 경우, 종료를 의미하므로, 0을 가중할 수 있도록 반환
   2. 한 발의 위치가 0보다 클 때, 양 발의 위치가 같으면 큰 수를 가중할 수 있도록 반환하여 최적의 수에서 제외
3. 재귀함수에서는 현재 단계와 발 위치에 따라 최소 힘을 반환
   1. 현재 상태에 대한 메모이제이션된 수가 존재할 경우, 그대로 반환
   2. 존재하지 않을 경우, 함수를 재귀적으로 호출하여 최소 힘을 구하여 메모이제이션 후 반환

03. 🛠️ 시도별 수정

1회차 

• 지시 사항의 단계(level)이 0번째부터 삽입되는데, 재귀 함수에서 level을 더해주는 것으로 첫 번째 지시를 넘겨버림
  -> 0번째부터 수행할 수 있도록 수정

2회차

---

04. 🗝️ 정답 코드

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;

vector<int> orders;
const int weight[5][5] = {
  {1, 2, 2, 2, 2},
  {INF, 1, 3, 4, 3},
  {INF, 3, 1, 3, 4},
  {INF, 4, 3, 1, 3},
  {INF, 3, 4, 3, 1}
};

int mem[int(1e5 + 1)][5][5];

int func(int level, int left, int right){
  if(level == orders.size() - 1) return 0;
  else if(left > 0 && left == right) return INF;

  int &cache = mem[level][left][right];
  if(cache != -1) return cache;

  int next_level = level + 1;
  int next_order = orders[level];

  return cache = min(
    func(next_level, next_order, right) + weight[left][next_order], 
    func(next_level, left, next_order) + weight[right][next_order]
  );
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  memset(mem, -1, sizeof(mem));

  do{
    int order;
    cin >> order;
    orders.push_back(order);
  }while(orders.back() != 0);

  cout << func(0, 0, 0) << "\n";

  return 0;
}