14238 출근 기록

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

#dp

14238번: 출근 기록

#골3 14238 출근 기록 답지

'''

답지를 본 이유

1. a,b,c의 경우만 살펴보고 다른 요소를 살피지 못함

2. 이 문제의 특성이긴 하지만 a b c 각각의 조건도 dp에 들어가야한다는 걸 배움

3. 문자열로 출력하기 위한 요소도 있어야한다.

4. join 함수로 문자열에 있는걸 쉽게 낼 수 있다.

5. go 함수 안에 느낌들을 좀 보면 Ture False 로 그 이후로 갈지를 결정후 안되면 -1 끝까지 되면 문자열 출력

이런 느낌이라는 걸 알 수 있으며 이 구현법 익힐 것.

'''

from sys import stdin

input=stdin.readline

S = input()

#S 출근 기록 입력

n = len(S)

#n 일자

dp = [[[[[0 for _ in range(3)] for _ in range(3)] for _ in range(51)] for _ in range(51)] for _ in range(51)]

#dp[a][b][c][p1][p2]

ans = [0] * 50

#ans = [0 ... 0] 50개 이후에 join 함수를 이용하여 문자열로 출력될 녀석이다

def go(a, b, c, p1, p2):

#go함수 a b c p1 p2 로 돌아감

    if a < 0 or b < 0 or c < 0:

        return False

#만약 쓸 수 있는 날짜를 넘겼다면 False

    if a == 0 and b == 0 and c == 0:

        return True

#다 썼으면 리턴    

    if dp[a][b][c][p1][p2]:

        return False

#탐색했었으면 False    

    dp[a][b][c][p1][p2] = True

#탐색 완료

    ans[n-a-b-c] = 'A'

#ans를 문자열이라고 생각한다. 처음 함수에 들어왔다면 n-a-b-c는 0으로 첫번째 알파벳이 'A'취급된다.    

   

    if go(a - 1, b, c, 0, p1):

        return True

#이전 것이 a인 다음 함수로 이동 되면 True

    if p1 != 1:

        ans[n-a-b-c] = 'B'

        if go(a, b - 1, c, 1, p1):

            return True

#이전 것이 b인 다음 함수로 이동 되면 True

       

    if p1 != 2 and p2 != 2:

        ans[n-a-b-c] = 'C'

        if go(a, b, c - 1, 2, p1):

            return True

#이전 것이 c인 다음 함수로 이동 되면 True

    return False

#통과 안되면 False

an = 0

bn = 0

cn = 0

# ""n은 ""이 나온 개수

for s in S:

    if s == 'A':

        an += 1

    elif s == 'B':

        bn += 1

    elif s == 'C':

        cn += 1

#an bn cn 만들기        

if go(an, bn, cn, 0, 0):

    print(''.join(ans[:n]))

#처음이니깐 p1 p2 는 0 0 이고 an bn cn 을 넣어서 join 함수로 문자열 출력 아니면 -1 출력    

   

else:

    print(-1)

 

dp를 활용하여 같은 포지션으로 go함수가 돌면 False로 되돌려버리는 알고리즘이다.

이는 나쁘진 않지만 좀 더 최적화가 있겠다 싶어서 찾아봤다.

 

#14238 출근 기록 최적화

def main():

    #시작

   

    global ansl

    #기록의 길이 ansl 전역함수화

   

    a = input()

    #a 입력

   

    ansl = len(a)

    #ansl 기록의 길이

   

    ans = -1

    #ans default 값 -1

   

    cCnt = [0, 0, 0]

    #a, b, c 기록

   

    for c in a:

       

        cCnt[ord(c) - 65] += 1

    #cCnt ord 함수를 이용해 0 에 A 1에 B 2에 C의 값이 들어가게 설정

       

    for i in range(3):

        #0 1 2 : A B C

        if cCnt[i] > 0:

            #만약 A B C가 나오는 횟수가 각각 0보다 크다면

           

            tmp = getans(i, [cCnt[0], cCnt[1], cCnt[2]])

            #tmp 함수에 돌려서 나오는 값이 tmp가 된다.

           

            if tmp != -1:

                ans = tmp

                break

            #문자열이 출력되면 ans를 문자열로 바꾼다.

           

    print(ans)

    #ans가 바뀌지 않았다면 -1 바뀌었다면 문자열 출력됨

   

def getans(sIdx, cntList):

   

    global ansl

    #똑같이 ansl 전역함수로

   

    word = chr(sIdx + 65)

    #word 기본 설정 첫값으로 (chr(65,66,67)=알파벳A,B,C)

   

    cntList[sIdx] -= 1

    #cntList에서 탐색중인 알파벳 개수 뺌

    #이제 그 알파벳을 넣었다고 생각하는거임

   

    dis = [51, 51, 51]

    # A로부터 거리, B로부터 거리, C로부터 거리

   

    dis[sIdx] = 0

    # 이전 알파벳을 이미 설정했음

   

    while 1:

        #반복문

       

        if len(word) == ansl:

            return word

        #조건 : 하나의 문자열이 생성되면 문자열 리턴

       

        left = ansl - len(word) - 1

        #지금 시행에서 붙이고 남은 길이

       

        maxB = left // 2

        #B를 붙일 수 있는 최대 갯수

       

        maxC = left // 3

        #C를 붙일 수 있는 최대 갯수

        #최대 갯수를 알면 내가 탐색중인 알파벳이 들어갔을때 유효한지 미리 알 수 있다.

       

        if left % 2 != 0:

            maxB += 1

        if left % 3 != 0:

            maxC += 1

        #최대 갯수 구체화

       

        if cntList[2] > 0 and cntList[1] <= maxB and dis[2] >= 2:

        #c의 갯수가 존재하고, b의 갯수가 b의 최댓수를 안넘고, c의 조건이 맞을때

            word += 'C'

            cntList[2] -= 1

            dis[0] += 1

            dis[1] += 1

            dis[2] = 0

            continue

       

        #a,b,c 거리 갱신/c갯수 갱신/word 갱신

        if cntList[1] > 0 and cntList[2] <= maxC and dis[1] >= 1:

        #b의 갯수가 존재하고, c의 갯수가 c의 최댓수를 안넘고, b의 조건이 맞을때

            word += 'B'

            cntList[1] -= 1

            dis[0] += 1

            dis[1] = 0

            dis[2] += 1

            continue

        #갱신

       

        if cntList[0] > 0:

        #a의 갯수가 존재할때

            word += 'A'

            cntList[0] -= 1

            dis[0] = 0

            dis[1] += 1

            dis[2] += 1

            continue

        #갱신

       

        break

   

    return -1

    #아무것도 없을때 -1 리턴

   

if __name__ == '__main__':

    main()