12026 BOJ 거리

💡문제 분석 요약

• 시작지점에서, 끝까지 가는데에 드는 최소비용을 계산한다.
• 이동은 반드시 B -> O -> J 순서로만 이동할 수 있고, 해당 알파벳이 인접해있지 않으면 점프도 가능하다.
• 점프할 때 드는 비용은 거리의 제곱만큼 든다.

💡알고리즘 설계

• DP를 이용해서 점프를 할 때 어디 알파벳으로 점프해야 최소비용일지 계산한다.
• 이중 for문으로 모든 원소에 대해서 비교한다.

💡코드

n = int(input())
boj = input()

# 여기서 dp[i]의 값은 해당 인덱스까지 가는데에 드는 에너지를 의미함.
# 문제 조건에서 적힌 N의 최대값이 1000이라서, 첫번째에서 마지막으로 바로 점프하더라도 1000000을 넘지 않음
dp = [1000000]*n
dp[0] = 0

for i in range(n):
    for j in range(i+1, n):
        if (boj[i]=="B" and boj[j]=="O") or (boj[i]=="O" and boj[j]=="J") or (boj[i]=="J" and boj[j]=="B"):
            dp[j] = min(dp[j], dp[i] + (j-i)**2 ) # j-i는 인덱스끼리 떨어진 거리를 의미

        # if문을 3개 써도 dp 비교하는 구문이 동일해서 or로 합침
        # if 3개와, or로 묶은 것은 or이 근소하게 빨랐는데, 큰 의미는 없을듯 (-36ms)

# for문이 끝났는데도 마지막 값이 안바뀌었으면 스타트가 링크를 만나지 못한 것임
if dp[-1] == 1000000:
    print(-1)
else:
    print(dp[-1])

💡시간복잡도

• 이중 for문을 사용해서 모든 경우를 다 봐야하므로 O(N^2)

💡 틀린 이유

• dp값 초기화를 처음에 dp = [1]*n 으로 했다. 바로 옆은 이동 거리가 1이니까 1로 초기화 했었는데, 그게 아니라 오히려 max 값으로 했어야했다. 왜냐하면 1로 설정하면 dp값을 업데이트할 때 min 함수에서 항상 기존의 값을 선택해서 업데이트가 안된다.
• dp를 업데이트할 때 점프하느냐, 1칸만 이동하느냐를 고민했었다. 왜냐하면 1칸만 이동하면 그냥 1을 더해주면 되기 때문이다. 그런데 1칸을 점프하는 것도 ( j-i )^2 으로 표현할 수 있었다. 2->3으로 점프하면 (3-2)^2 이므로 1이라서, 1만 더해주는 것을 의도할 수 있었다.

💡 틀린 부분 수정 or 다른 풀이

• dp값을 최대값으로 수정함.
• inf를 이용해서 최대값을 지정할 수 있었음.

max_count = float("inf")
dp = [max_count]*N

💡 느낀점 or 기억할정보

• 최대값 설정시 쓰는 float("inf") 알고있기 !!!