백준 20047번 동전 옮기기

김두현·2023년 2월 20일
1

백준

목록 보기
104/133
post-thumbnail

🔒[문제 url]

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


🔑알고리즘

SS에서 선택한 두 동전을 제외한 순서에서, 두 동전을 재배치함으로써 TT를 만들어야한다.
SS에서 두 동전을 제외한 순서를 KK라고 하자.

  • KKTT의 배치를 앞에서부터 비교해가며 배치할 동전을 결정한다.
    배치할 방법은 다음과같이 2가지이므로, DFS를 진행한다.
  1. 현재 KK의 동전과 현재 TT의 동전이 같을 경우, KK의 동전을 배치한다.
  2. 현재 KK의 동전과 현재 TT의 동전이 같을 경우, SS에서 제외했던 동전을 배치한다. 이때, 제외한 동전은 2개임에 주의하여 배치한다.

🐾부분 코드

bool DFS(int idx,int tIdx,int cnt)
{//K의 idx , T의 idx , 배치한 동전의 수
	bool rtn = false;
    
    //끝까지 배치했다면 true 반환
	if(tIdx == n) return rtn = true;

    //제외한 동전 중 하나를 순서에 맞게 배치
	if(cnt != 2 && coin[cnt] == T[tIdx])
        //제외한 동전의 수는 2개이므로 cnt != 2여야한다.
		rtn = max(rtn,DFS(idx,tIdx+1,cnt+1));
    //현재 K의 동전를 배치
	if(K[idx] == T[tIdx])
		rtn = max(rtn,DFS(idx+1,tIdx+1,cnt));

	return rtn;
}

<DFS 함수>
위에서 설명한 2가지 배치 방법에 따라 DFS를 진행한다.
제외한 동전을 배치할 때, 이미 제외된 동전을 배치한 갯수와 배치 순서에 유의한다.



void SOLVE()
{
	coin[0] = S[l]; coin[1] = S[r];
	for(int i = 0; i < n; i++)
		if(i != l && i != r)
			K += S[i];

	if(DFS(0,0,0)) cout << "YES";
	else cout << "NO";

}

<제외한 동전과 K 초기화>
DFS를 위해 SS에서 옮길 두 동전을 제외한 배치 KK를 초기화한다.


🪄전체 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n;
string S,T;
int l,r;

char coin[2];//제외한 동전
string K = "";//S에서 선택한 동전을 제외한 후의 동전 배치

void INPUT()
{
	IAMFAST
	cin >> n >> S >> T >> l >> r;
}

bool DFS(int idx,int tIdx,int cnt)
{//K의 idx , T의 idx , 배치한 동전의 수
	bool rtn = false;
    
    //끝까지 배치했다면 true 반환
	if(tIdx == n) return rtn = true;

    //제외한 동전 중 하나를 순서에 맞게 배치
	if(cnt != 2 && coin[cnt] == T[tIdx])
        //제외한 동전의 수는 2개이므로 cnt != 2여야한다.
		rtn = max(rtn,DFS(idx,tIdx+1,cnt+1));
    //현재 K의 동전를 배치
	if(K[idx] == T[tIdx])
		rtn = max(rtn,DFS(idx+1,tIdx+1,cnt));

	return rtn;
}

void SOLVE()
{
	coin[0] = S[l]; coin[1] = S[r];
	for(int i = 0; i < n; i++)
		if(i != l && i != r)
			K += S[i];

	if(DFS(0,0,0)) cout << "YES";
	else cout << "NO";

}

int main()
{
	INPUT();
	SOLVE();
}

🥇문제 후기

흠... 문제를 보자마자 DFS 코드를 작성하고 One try AC를 받은 케이스라,
태그를 열어보니 DP라서 조금 놀랐다.
이미 배치한 동전은 유지된 채 계속 진행돼서 그런건가..?!
다만, 확실히 빠르게 DFS 풀이를 떠올리는게 쉽지는 않은 것같다.


💕오류 지적 및 피드백은 언제든 환영입니다. 복제시 출처 남겨주세요!💕
💕좋아요와 댓글은 큰 힘이 됩니다.💕
profile
I AM WHO I AM

0개의 댓글