[백준/C++] 25824번 빠른 오름차순 메시지 전달

---

그냥 주위 친구가 풀어낸 거 보고 나도 풀어볼까? 하고 문제를 풀게 되었다.

문제를 처음 봤을 때는 BFS / 다익스트라 or 플로이드와샬 이라고 생각했는데 BFS로만 풀릴 것 같았다.

다시 생각해보니 input이 12로 제한되어있고 이진트리로 가지치며 나오는 최종 경우의 수를 생각해봐도 leaf에서 2^6으로 모든 경우의 수가 128보다 적다. 3초나 주어지는 것을 보니 브루트포스로 풀어낼 수 있을 것 같았다.

 

풀며 식을 세우다가 느꼈는데 DP로 식을 세울 수 있어 보였다. 물론 dp식을 세우는데 실패해서 시간을 낭비하고 브루트포스로 구현하였지만 맞춘사람을 보니 BFS와 DP로 풀어낸 경우도 확인할 수 있었다. 브루트포스를 이진트리 느낌으로 구현하다보니 조금 귀찮아 골드 문제가 아니였나 싶다.

---

#include<bits/stdc++.h>
using namespace std ;
vector< vector<int> > input(12, vector<int>(12)) ;
vector< vector< pair< int, int> > > answer(6) ;
int main()
{
    cout << 1e9;
    ios::sync_with_stdio(0), cin.tie(0) ;

    for(int i = 0 ; i < 12 ; i++)
        for(int j = 0 ; j < 12 ; j++)
            cin >> input[i][j] ;
    
    answer[0].push_back(make_pair(input[0][1], 1)) ;
    answer[0].push_back(make_pair(input[1][0], 0)) ;

    for(int i = 1 ; i < 6 ; i++)
    {
        for(int j = 0 ; j < answer[i-1].size() ; j++)
        {
            int first = answer[i-1][j].first + input[answer[i-1][j].second][i*2] + input[i * 2][i * 2 + 1];
            int second = answer[i-1][j].first + input[answer[i-1][j].second][i*2 + 1] + input[i * 2 + 1][i * 2];
            answer[i].push_back(make_pair(first, i * 2 + 1)) ;
            answer[i].push_back(make_pair(second, i * 2)) ;
        }
    }
    int real_answer = 0x3f3f3f3f ;
    for(pair<int,int> tmp : answer[5])
        if(tmp.first < real_answer) real_answer = tmp.first ;
    
    cout << real_answer ;
}

---

느낀점: dp나 BFS로 구현한 코드들을 보고 다음에 이해해봐야겠다.
문제: https://www.acmicpc.net/problem/25824

25824번: 빠른 오름차순 메시지 전달