다이나믹 프로그래밍6 [백준 Platinum 5] 2618 경찰차 - Java 문제링크 : https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 접근 과정 : DP를 활용하려고 했다. DP를 활용해서 최소 거리를 갱신하는데, 상황별 경찰차의 위치를 어떻게 처리할지가 관건이라고 생각했다. 경찰차의 위치는 사건이 발생한 위치와 같아지므로.. 최근에 각 경찰차가 처리한 사건의 인덱스를 기준으로 DP했다. 그리고 한번 더 탐색하면서, 경로를 저장했다. 소스 코드 및 결과 : package BOJ; /* 경찰차 .. 2022. 1. 4. [백준 Gold 4] 21923 곡예 비행 - Java 문제링크 : https://www.acmicpc.net/problem/21923 21923번: 곡예 비행 동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 www.acmicpc.net 접근 과정 : 상승 비행과 하강 비행을 따로 관리 (상승 구간과 하강 구간이 중복되는 칸이 1~N개 있다!!!) 상승 비행이 끝나는 칸 == 하강 비행이 시작하는 칸 비행 점수 = (r,c)까지 상승한 경우 + (r,c)부터 하강하는 경우 DP로 하강 비행을 탐색하고 하강 비행 탐색 로직 내부에서 상승 비행 탐색을 수행 하강비행 = (r,c)까지 상승비행 + (r,c)부터 하강비행 OR (.. 2021. 12. 16. 이전 1 2 다음
