[BAE/<JOON> 문제풀이] 2342. DDR

https://www.acmicpc.net/problem/2342

2342번: Dance Dance Revolution

오늘 너무 늦어서 풀이는 내일씀..

 

// 2342.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

int dp[100001][5][5];

int main()
{
    int im = -1;
    vector<int> arr;
    int value[5][5] = {
        { 0, 2, 2, 2, 2 },
        { 2, 1, 3, 4, 3 },
        { 2, 3, 1, 3, 4 },
        { 2, 4, 3, 1, 3 },
        { 2, 3, 4, 3, 1 },
    };
    while (im != 0) {
        cin >> im;
        arr.push_back(im);        
    }    
    int n = arr.size();    
    memset(dp, 999999, sizeof(dp));
    dp[0][0][0] = 0;    
    for (int i = 1; i < n; i++) {
        int now = arr[i - 1];
        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < 5; k++) {
                if (dp[i][j][now] > dp[i - 1][j][k] + value[now][k]) {
                    dp[i][j][now] = dp[i - 1][j][k] + value[now][k];
                }
                if (dp[i][now][k] > dp[i - 1][j][k] + value[j][now]) {
                    dp[i][now][k] = dp[i - 1][j][k] + value[j][now];
                }
            }
        }
    }
    int mn = 999999;
    for (int i = 1; i < 5; i++) {
        for (int j = 1; j < 5; j++) {
            if (dp[n - 1][i][j] < mn && dp[n - 1][i][j] != 0) mn = dp[n - 1][i][j];
        }        
    }
    /*for (int k = 0; k < n; k++) {        
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (dp[k][i][j] == 1061109567) {
                    cout << "-1 ";
                    continue;
                }
                cout << dp[k][i][j] << " ";
            }            
            cout << "\n";
        }
        cout << "\n";
    }*/
    cout << mn;
    return 0;
}

// 프로그램 실행: <Ctrl+F5> 또는 [디버그] > [디버깅하지 않고 시작] 메뉴
// 프로그램 디버그: <F5> 키 또는 [디버그] > [디버깅 시작] 메뉴

// 시작을 위한 팁: 
//   1. [솔루션 탐색기] 창을 사용하여 파일을 추가/관리합니다.
//   2. [팀 탐색기] 창을 사용하여 소스 제어에 연결합니다.
//   3. [출력] 창을 사용하여 빌드 출력 및 기타 메시지를 확인합니다.
//   4. [오류 목록] 창을 사용하여 오류를 봅니다.
//   5. [프로젝트] > [새 항목 추가]로 이동하여 새 코드 파일을 만들거나, [프로젝트] > [기존 항목 추가]로 이동하여 기존 코드 파일을 프로젝트에 추가합니다.
//   6. 나중에 이 프로젝트를 다시 열려면 [파일] > [열기] > [프로젝트]로 이동하고 .sln 파일을 선택합니다.