12026 BOJ 거리

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

12026번: BOJ 거리

#12026 BOJ거리

 

import sys

 

input=sys.stdin.readline

n=int(input())
#n 입력

l=list(input())
#l 입력

dp=[1001*1001 for i in range(n)]
#dp 생성

dp[0]=0
#dp 초기값 설정

#2가지 생각을 해야겠지.
#1. 이것이 다음 순서에 나온 문자인가?
#2. 이전꺼를 볼때 이전문자를 가진 애가 있는가? 여러가지면 어떤게 에너지가 더 작게 드는가?

for i in range(n):
    k=0
#에너지
    for j in range(i-1,-1,-1):
        k+=1
        if (l[i]=='B' and l[j]=='J') or (l[i]=='O' and l[j]=='B') or (l[i]=='J' and l[j]=='O'):
            dp[i]=min(dp[i],dp[j]+k*k)

#이전꺼를 하나씩 봐서 조건에 맞는 에너지가 최소값으로 드는 dp 를 찾아본다.

print(dp[n-1] if dp[n-1]!=1001*1001 else -1)

#답 초기값이면 -1 아니면 dp[n-1]

 

#시간이 너무 오래걸리기도 했고 뭔가 새로운 방법이 있을 것 같아서 다른 사람 코드를 더 찾아보게 되었다. 그러다 #enumerate 를 이용해서 b o j 에 저장해서 각각 보는 방법을 찾게 되었다.

 

#2

n=int(input())
#n 입력

l=list(input())
#리스트 입력

B=[]
O=[]
J=[]
#리스트와 동일한 글자가 있는 인덱스를 저장하는 리스트들 생성

for index,word in enumerate(l):
    if word == 'B':
        B.append(index)
    if word == 'O':
        O.append(index)
    if word == 'J':
        J.append(index)

#enumerate가 인덱스와 안의 내용을 둘다 뽑아낸다는 걸 이용하여 내용이 같으면 인덱스를 넣는 for문 생성

energy=[-1]*(n)
energy[0]=0
#energy의 초기값은 False로 해도 될 정도로 상관없지만 조건에 안맞으면 -1을 출력하라고 했으니 -1로 다 설정해준다.

#아무런 움직임이 없을때는 0

for i in range(1,n):
    try:
        if l[i]=='O':
            energy[i]=min([energy[j]+(i-j)**2 for j in B if j<i if energy[j]!=-1])
        elif l[i]=='B':
            energy[i]=min([energy[j]+(i-j)**2 for j in J if j<i if energy[j]!=-1])
        else:
            energy[i]=min([energy[j]+(i-j)**2 for j in O if j<i if energy[j]!=-1])
    except:
        pass

#이제 세가지가 여기서 다 들어간다. 우선 j가 처음 탐색하는게 아니여야한다는것,  두번째 i보다 더 작은 수여야 한다는#것 3번째 이전의 것중에서 가장 최소값이여야한다는것,

print(energy[n-1])

#답 작성

 

#우선 enumerate를 이용하여 쓸데없이 탐색하는 것들을 없애고 최적화 시켰다는 점에서 배울 점이 있는 것 같다. 인덱 #스를 활용하는 문제가 나왔을때 생각해야할 문제인듯