[Programmers] GPS

알고리즘/programmers

꾸준함. 2022. 7. 9. 11:32

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

DP 알고리즘을 통해 풀 수 있는 문제였습니다.

알고리즘은 아래와 같습니다.

1. cache[k][v]는 거쳐간 k번째 거점이 v일 경우 누적 수정된 횟수를 저장하는 캐시 배열입니다.

2. cache를 모두 INF로 초기화하고 주어진 문제에서 승차와 하차 위치가 오류가 없다고 했으므로 승차 위치를 firstGps, 하차 위치를 lastGps로 지정하고 cache[0][startGps]을 0으로 초기화합니다.

3. 출발지 이후의 거점들을 순회하면서 해당 위치가 u로 수정되었을 경우 누적 수정된 횟수를 저장해줍니다.

4. 3번을 진행한 후 gps_log의 (k - 1)번 째 위치로 lastGps를 선정할 수 있는 경우 cache[k - 1][lastGps]가 INF가 아닐 것입니다.

4.1 INF일 경우 올바른 경로로 수정 불가능한 케이스이므로 -1을 반환해줍니다.

4.2 INF가 아닐 경우 올바른 경로이므로 cahce[k - 1][lastGps]를 반환해줍니다.

개발환경: Programmers IDE

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

꾸준함