Notice
Recent Posts
Recent Comments
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
Tags
more
Archives
Today
Total
관리 메뉴

No Limitation

[구현] A와 B (백준 12904) 본문

프로그래밍

[구현] A와 B (백준 12904)

yesungcho 2024. 4. 1. 14:10

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

 

12904번: A와 B

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

www.acmicpc.net

아이디어를 공부하면 좋을 거 같은 문제

 

이 문제를 푸신 다른 분들 풀이가 좋아서 공부하면 좋을 듯

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

 

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

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스

growth-coder.tistory.com

https://chocochip101.tistory.com/entry/%EB%B0%B1%EC%A4%80-12904%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC-A%EC%99%80-B

 

[백준] 12904번 - A와 B (파이썬) 문제 및 풀이

문제) 백준 - 그리디 알고리즘(Greedy) - A와 B -> www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양

chocochip101.tistory.com

 

초반에 열심히 DFS 문제인 줄 알고 아래 코드처럼 풀었는데 시간 초과... DP 까지 써가면서 발악했지만 시간 초과를 넘지 못함

import copy
import sys
S = sys.stdin.readline().strip()
T = sys.stdin.readline().strip()

def do_reverse(src) :
    src = list(src)
    src.reverse()
    src = ''.join(src)

    return src

def DFS(src,tgt,memo={}) :
    if src in memo :
        return memo[src]
    
    if src == tgt :
        return True
    if len(src) > len(tgt) :
        return False

    memo[src] = DFS(src+'A',tgt) or DFS(do_reverse(src)+'B',tgt)
    return memo[src]

print(int(DFS(S+'A',T) or DFS(do_reverse(S)+'B',T)))

 

그래서 계속 고민하다 다른 풀이를 참고해보니, 결국 이건 "역으로 푸는 문제"였음

 

즉 S->T로 갈 때는 두 가지 루트가 존재하지만

 

T->S 일때는 이미 T는 주어진 결과이므로 하나의 루트만 존재하게 된다.

 

예를 들어 T가 ABBA일 때

T의 끝 값은 A이므로 S에서는 ABB에서 A를 추가했을 것이다.

 

반대로 T가 ABBB라고 하면 끝에가 B이므로

BBA에서 뒤짚어 ABB를 만든다음 B를 추가했을 것이다.

 

이렇게 역추적하면 빠른 시간 내에 S를 찾을 수 있게 되고 그것이 주어진 S와 같은 지만 체크하면 된다. 

import copy
import sys
S = sys.stdin.readline().strip()
T = sys.stdin.readline().strip()

def do_reverse(src) :
    src = list(src)
    src.reverse()
    src = ''.join(src)
    return src

flag = False
### T가 S보다 줄어들면 볼 필요도 없지.. 같을 수가 없으니
### 종료 조건에 유의하자
while len(T)>len(S) :
    if T[-1] == 'A' :
        T = T[:-1]
        if T == S :
            flag = True
            break
    if T[-1] == 'B' :
        T = T[:-1]
        T = do_reverse(T)
        if T == S :
            flag = True
            break

print(int(flag))

 

역추적으로 푸는 비슷한 문제로 백준 11501 문제도 있다니 참고하면 좋을 듯

 

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

 

11501번: 주식

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타

www.acmicpc.net