python 백준 2602 돌다리 건너기

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

로직

• dp 문제, 조금 복잡

• 다리의 왼쪽부터 오른쪽으로 순회

• 다리의 종류(천사,악마) 별로 적혀진 알파벳이 다름

• 다리에 적혀진 알파벳이, 만들어야 하는 문자열에 어디에 쓰이는지 확인

  • 예를 들어 "RIRNRGRS" 라는 문자열에서 R은 [0,2,4,6]에서 사용됨
  • 다리에 적힌 알파벳이 R이라면 0번, 2번, 4번, 6번에서 사용 될 수 있음
  • 2,4,6번의 경우 조건이 완성된 경우에 사용이 가능
  • 2번을 예시로 들면 그 전에 R과 I가 완성 되어 있는 경우 사용 가능

• 다리를 idx번 지났을때, 문자열의 완성 정도를 기록

  • 다리4칸을 건넜을 때, 문자열이 1번까지 완성되는 경우의 수 3개, 2번까지 완성된 경우의 수 1개 ....

예시

• 예제 1번 문자열:RGS, 악마: RINGSR, 천사:GRGGNS 이 주어졌을 경우
• 악마기록 : [0,0,0], 악마기록 : [0,0,0] 으로 초기화 (3칸인 것은 만들려는 문자열이 3칸이기에)
• 다리 왼쪽부터 순회

  첫번째 턴(다리 0번)

• 악마 다리는 R, 천사 다리는 G
• 천사 기록: [0,0,0] 그대로
  • G를 사용하는 경우는 문자열 1번인데, 그 전에 악마다리에서 첫번째까지 완성된 경우의 수가 0(악마 기록[0])
• 악마 기록:[1,0,0] 변화
  • R이 사용 되는 곳은 문자열의 0번, 사전 조건이 없어 바로 추가
  • 0번까지 완성된 경우의 수가 1개 증가했으므로 0->1로 변경

두번째 턴(다리 1번)

• 악마 다리는 I, 천사 다리는 R
• 악마 기록 : [1,0,0] 그대로, I는 문쟈열에서 사용되지 않기에 pass
• 천사 기록 :[1,0,0]으로 변화
  • R은 문자열의 0번째에서 사용

    세번째 턴(다리 2번)

• 악마 다리는 N, 천사 다리는 G
• 악마 기록 : [1,0,0] 그대로, N은 문자열에서 사용X
• 천사 기록 : [1,1,0] 변화
  • G는 문자열에서 1번째에서 사용됨
  • 이를 위해선 악마다리에서 0번까지 완료된 경우가 필요
  • 악마다리에서 0번까지 완료된 경우의 수는 1개(악마기록[0] == 1)이므로 0->1로 변화

    네번쨰 턴 (다리3번)

• 악마 다리는 G, 천사 다리는 G
• 악마 기록 : [1,1,0] 변화
  • G는 문자열에서 1번째에서 사용됨
  • 이를 위해선 천사다리에서 0번까지 완료된 경우가 필요
  • 천사다리에서 0번까지 완료된 경우의 수는 1개(천사기록[0] == 1)이므로 0->1로 변화
• 천사 기록 : [1,2,0]변화
  • 마찬가지로 악마다리에서 0번까지 완료된 경우의 수(악마기록[0] == 1) 만큼 증가하여 1->2로 변화

다섯번째 턴 (다리4번)

• 악마 다리는 S, 천사는 N
• 악마 기록 : [1,1,2] 변화
  • S는 문자열 2번쨰에서 사용됨
  • 이를 활용하기 위해서는 천사 다리에서 1번까지 완성된 경우가 필요
  • 그렇기에 악마 기록[2]가 천사 기록[1] == 2만큼 추가

나머진 생략

# 코드는 다리가 2개가 아닌 3,4,5 ... 개로 늘어나면 어떻게 하지?라는 생각으로 작성하여 복잡

def solution(sentence:str,bridge:list[str])->int:
    # 각 알파벳 idx들 기록
    alphaTotal = {"R":[],"I":[],"N":[],"G":[],"S":[]}
    S = len(sentence)
    for i in range(S):
        alpha = sentence[i]
        alphaTotal[alpha].append(i)

    B = len(bridge)
    L = len(bridge[0])
    check = [[0]*S for _ in range(B)]
    for idx in range(L):    # 다리idx 
        temp = list()    # temp를 사용하는 이유는 각 다리의 변화를 한번에 업데이트 하기 위함
        for i in range(B):  # 어떤 다리인지, 천사 or 악마 다리
            alpha = bridge[i][idx]
            for num in alphaTotal[alpha]:    # num은 해당 알파벳이 문자열에서 사용되는 위치
                if num == 0:
                    temp.append((i,num,1))
                else:
                    value = 0 # 자기 다리를 제외한 경우의 수의 합
                    for v in range(B):
                        if v == i:continue
                        value += check[v][num-1]
                    temp.append((i,num,value))
        for r,c,cnt in temp:
            check[r][c] += cnt
    ansValue = 0
    for i in range(B):
        ansValue += check[i][S-1]
    return ansValue
sentence = input()
devil = input()
angle = input()
ans = solution(sentence,[devil,angle])
print(ans)