[백준 python] 12904번 A와 B 그리디

[백준 python] 12904번 A와 B 그리디

레벨: 골드 5

언어: python

---

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

12904번: A와 B

📑풀이 과정

이번 문제는 첫째 줄인 S를 T로 만들려고 하면 많이 복잡해 진다.

 

S -> T

예시 1번 처럼 B를 ABBA로 만들기 위해

B에서 BA가 될 수 있고 BB가 될 수 있다. 또 BA와 BB가 두가지 선택이 가능해서 4개가 된다.

1 -> 2 -> 4  로 선택 가지가 x^2으로 커진다.

 

T->S

이때 생각을 바꿔서 T를 S로 만들면 쉽게 할 수 있다.

예시 1번에서 ABBA를 B로 만들기 위해

 

1. 마지막 문자가 A이면 A를 삭제하고 B이면 B를 지우고 문자열을 뒤집으면 된다.

2. T가 S와 같아질때 까지 반복하고 같지 않으면 0을 출력한다.

📋풀이 코드

import sys

input = sys.stdin.readline

S = list(input().strip())
T = list(input().strip())

while len(T) >0:
  if S == T:
    print(1)
    exit()
  if T.pop() == 'A':
    continue
  else:
    T.reverse()

print(0)

💻 코드 라인별 풀이

👍다른 사람 풀이

---