22.06.21. 풀었던 문제들

1. GPS

bellman-ford로 푸는 문젠가? 싶어서 생각해 봤는데 '잘못된 길'을 찾는 시점부터 뭔가를 해결하려 하면 끝이 없을 것 같아서 포기

DP라는 걸 알게 되어서 dp[i][j]를 time i to j까지 최소수정 횟수를 두려 했는데, 이렇게 해서 dp[0][0]부터 시작하려 했다. 그런데 음... 아니었다. {0, 0}, {1, 1}, ... {n, n}을 고치고 {0, 1}, {1, 2}, ... 를 고치는 방식은 모든 위치 정보를 넣어야 하기도 했다. 시간 초과가 날 알고리즘이기도 했고. 그래서 다른 방식을 고민하다 ㅏ아... 모르겠다 싶어서 구글링

dp[t][l] = 시간 t의 위치가 l일 때, 시간 0부터 t까지경로를 수정해야 하는 최소 횟수로 생각하면, dp[t][l] = min(dp[t-1][l의 edge들 + l] + gps_logs[t] == l ? 1 : 0)으로 표현할 수 있다.

​

그리고 프로그래머스 lv3까지 올솔을 했다!