[ICPC] 백준 20047 - 동전 옮기기

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

힌트

선택한 동전은 단 두 개다. 완전 탐색을 해도 분기가 많이 발생하지 않는다.

풀이

동전 두 개의 위치를 바꿔가면서(그들의 상대적인 순서는 유지하고) T와 같은 배치를 만들 수 있는지 묻는 문제다.

 

배치 S에서 주어진 index에 해당하는 동전을 따로 뺀 뒤 동전을 처음부터 배치한다고 하면 다음 분기로 배치를 결정할 수 있다.

 

동전 두 개를 제거한 S의 배치 순서를 pos라 하고 T의 순서를 idx라 한다면

 

1. S[pos]와 T[idx]가 일치하면 그대로 놓기

 

2. T[idx]와 동전 두 개 중 하나를 조건에 맞게 놓기

 

이를 DFS로 구현하면 정답을 받을 수 있다. 자세한 구현은 밑에 소스를 참조한다.

 

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int n;
string s, t;
int a, b;
char ch[2];
string x;
int ans;
bool fin;

void dfs(int idx, int pos, int cnt)
{
  if (fin) return;

  if (idx == t.size())
  {
    ans = 1;
    fin = true;
    return;
  }

  if (cnt != 2 && ch[cnt] == t[idx]) dfs(idx + 1, pos, cnt + 1);
  if (x.size() != pos && t[idx] == x[pos]) dfs(idx + 1, pos + 1, cnt);
}

void solve()
{
  cin >> n >> s >> t >> a >> b;
  ch[0] = s[a];
  ch[1] = s[b];

  for (int i = 0; i < s.size(); ++i)
  {
    if (i == a || i == b) continue;
    x.push_back(s[i]);
  }

  dfs(0, 0, 0);
  if (ans) cout << "YES";
  else cout << "NO";
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}

제출 기록