[20/05/24] I 팬케이크 쌓기(12744)

처음에 나름 규칙 찾았다고 기뻐했는데 아니었음ㅋㅋ

알고보니 완전탐색으로 하나하나 뒤집어 보면 해결된다.

 

BFS 사용해서 하면 된다고 해서 다른 문제 풀려고 했는데 결국 BFS와 마주해야 했습니다

이것도 코드 안 보고 다시 짜봐야지

 

기억나는 게

- 뒤집는 함수

- 옳은지 확인하는 함수

- 큐로 다음 확인할 부분 저장

- pair로 하나는 n저장 하나는 +,- 저장

 

음.. 이정도? 함 짜봐야 겠다

 

bool check(vector<ii> v)
{
    for (int i = 1; i <= v.size(); i++)
    {
        if (i != v[i].first && v[i].second != 1)
            return false;
    }
    return true;
}

void line(vector<ii> v, int k)
{
    for (int i = 0; i < k; i++)
    {
        v[i].first = k - i;
        v[i].second = (v[i].second + 1) % 2;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    vector<ii> v(n);
    for (int i = 0; i < n; i++)
    {
        char t;
        scanf("%d %c", &v[i].first, &t);
        
        if (t == '+')
            v[i].second = 1;
        else
            v[i].second = 0;
    }
    
    
    
    
    return 0;
}

 

bfs 부분이 기억 안 난다...

 

아 그리고 뒤집는 함수 잘못 짰네. 이거 reverse하고 부호 바꿨어햐 했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

bool is_ok(vector<ii> v, int n)
{
    for (int i = 0; i < n; i++)
    {
        if (i+1 != v[i].first || v[i].second != 1)
            return false;
    }
    return true;
}

vector<ii> flip(vector<ii> v, int k)
{
    reverse(v.begin(), v.begin() + k);
    
    for (int i = 0; i < k; i++)
    {
        v[i].second = (v[i].second + 1) % 2;
    }
    
    return v;
}

int main() {
    int n;
    scanf("%d", &n);
    
    vector<ii> v(n);
    for (int i = 0; i < n; i++)
    {
        char t;
        scanf("%d %c", &v[i].first, &t);
        
        if (t == '+')
            v[i].second = 1;
        else
            v[i].second = 0;
    }
    
    queue<vector<ii>> q;
    map<vector<ii>, int> m;
    q.push(v);
    m[v] = 0;
    while (!q.empty())
    {
        vector<ii> check = q.front();
        q.pop();
        
        if (is_ok(check, n))
        {
            printf("%d", m[check]);
            break;
        }
        
        for (int i = 0; i < n; i++)
        {
            vector <ii> input = flip(check, i+1);
            
            if (m.find(input) != m.end())
                continue;
            
            q.push(input);
            m[input] = m[check] + 1;
        }
    }
    
    return 0;
}

끝.. 

 

어렵다기 보단 아직 낯설다

 

큐에 확인할 것들 넣어두고 하나씩 뺀 다음 맞으면 출력 아니면 1부터 n까지 확인하고.

 

확인할 때 map으로 이미 확인 한 거면 패스하고

 

아니라면 큐에 넣고 map의 확인 횟수를 늘리고..

 

약간 느낌에 bfs dfs 얘들은 재귀 써야한다는 그런게 있었는데 재귀 안 쓰고 큐 썼구나