프로그래머스 - 예상 대진표 [C++]

비교적 간단한 문제.

문제 유형은 DP 라고 생각한다. 이유는 공식 하나만 잡으면 풀리기 때문에.

그 공식이란 각각의 대진 인원들에 대해 {해당 인원의 번호, 타겟여부} 를 저장하고

round를 올려가며 대진을 돌리면서 타겟여부가 true인 사람끼리 붙게 되면 바로 round를 리턴하면 끝.

 

아래는 정답코드이다.

돌아가는 과정을 출력해보려면 주석을 해제하고 돌려보자.

 

#include <iostream>
#include <vector>

using namespace std;

int solution(int n, int a, int b)
{
    int round = 0;

    vector<pair<int, bool> > allV;
    for (int i = 0; i < n; i++)
    {
        if (i == a - 1 || i == b - 1)
            allV.push_back({i, true});
        else
            allV.push_back({i, false});
    }
    
    // cout << "first allV\n";
    // for (int i = 0; i < allV.size(); i++)
    //     cout << allV[i].first << "," << allV[i].second << " ";
    // cout << "\n\n";
    
    
    while (true)
    {
        round++;
        vector<pair<int, bool> > newV;
        for (int i = 0; i < allV.size(); i += 2)
        {
            if (allV[i].second == true && allV[i + 1].second == true)
                return round;
            else
            {
                if (allV[i].second == true)
                    newV.push_back(allV[i]);
                else
                    newV.push_back(allV[i + 1]);
            }
        }
        allV = newV;
        // for (int i = 0; i < allV.size(); i++)
        // {
        //     cout << allV[i].first << "," << allV[i].second << " ";
        // }
        // cout << "\n";
    }
    return round;
}