본문 바로가기
백준 알고리즘/그리디

[백준 12904][파이썬][그리디] A와 B

by 웅대 2023. 7. 16.
728x90
반응형

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

 

12904번: A와 B

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수

www.acmicpc.net

 

두 가지 연산을 통해 S에서 T로 바꿀 수 있는지 판단하는 문제이다.

 

처음에는 S에서 T로 바꾸는 방식으로 시도를 했는데 굉장히 까다로웠다.

 

S에서 T로 바꾸는 방식은 하나의 단계마다 여러 가지 경우의 수가 존재하기 때문에 신경써야하는 부분이 많다.

 

그런데 T에서 S로 바꾸는 방식은 하나의 단계마다 단 하나의 경우의 수만 존재한다.

 

길이가 4인 문자열의 마지막 단어는 무조건 'A' 아니면 'B'인데

 

만약 마지막 단어가 'A'라면 길이가 3인 특정 문자열의 뒤에 'A'를 붙였을 것이다.

 

만약 마지막 단어가 'A'라면 길이가 3인 특정 문자열의 뒤집어서 뒤에 'B'를 붙였을 것이다.

 

백준 11501번 문제처럼 거꾸로 생각해서 푸는 문제이다.

https://growth-coder.tistory.com/225

 

[백준 11501][파이썬] 주식 (그리디, 재귀)

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이

growth-coder.tistory.com

 

거꾸로 생각해보는 습관을 기르자.

 

import sys
input=sys.stdin.readline
s=input().rstrip()
t=input().rstrip()
while(len(t)>len(s)): # t의 길이가 s와 같아질 때까지
    if t[-1]=='A': # 마지막 A면 빼버림
        t=t[:-1]
    else: # 마지막 B면 빼고 뒤집음
        t=t[:-1]
        t=t[::-1]
print(1 if s==t else 0)
728x90
반응형

댓글