[Python] 백준 3806 S를 T로

문제 링크 :https://www.acmicpc.net/problem/3806

3806번: S를 T로

 

1. 접근 방법

접은 방법을 조금 고민했는데, 가능한 조건이 많지는 않지만, BFS나 DP로는 적합하지 않을 것 같아 그리디한 방식을 탐색했다.

---

2. 풀이 코드

🖥python 코드 링크 :https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/3000/3806.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

📕코드 해설

우선 문자열의 각 자리마다, S에서 T의 각 위치마다 튜플로 묶어 저장했다.

각 부분은 문자열로, 즉 '0', '1', '?'로 저장되지만, 이 글에서는 따옴표를 제외하고 작성함.

S	0	1	?	?	0	0
T	0	0	1	0	1	0
	(0, 0)	(1, 0)	(?, 1)	(?, 0)	(0, 1)	(0, 0)

이 때, 0에서 0으로, 1에서 1로 변경되는 경우는 무시해도 된다. 그래서 나머지 전후 변경되는 조건은 (0, 1), (1, 0), (?, 0), (?, 1)만 남게 된다. 그리고 여기서 각 조건을 어떻게 처리할지 고민해야 한다.

그리고 S문자열에서의 연산으로 변경되는 것을 교환이라고 이 글에서 작성했다.

 

1. (1, 0)을 제외한 나머지는 주어진 조건으로 해결할 수 있다. 그러므로 (1, 0)을 어떻게 해결할지 고민하는게 가장 중요하다.

2. 만약 (1, 0)과 (0, 1)을 교환한다면, 한 번의 연산으로 해결할 수 있다.

3. 만약 (1. 0)과 (?, 1)을 교환한다면, 두 번의 연산으로 해결할 수 있다.

 

이 조건을 고려하여, (1, 0)을 순서대로 (0, 1), (?, 1)과 교환하고, 연산횟수는 각각 1, 2회씩 더한다.

이 연산을 끝내고 (1, 0)이 남는다면 방법이 없으므로 -1을, 만약에 남지 않는다면 나머지 (0, 1), (?, 0), (?, 1)의 개수만큼 출력값에 더한다.

---

3. 생각 정리

나름 조건은 단순해서, 하나하나 이어나가며 해결했다.