백준 2157 자바 - 여행 (BOJ 2157 Java)

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

 

  입력 받으면서 서쪽에서 동쪽으로 이동하는 경우는 제외해줬다. (a가 b보다 큰 경우) 동일 노선에 기내식이 별로인 경우도 제외해줌.

 

처음엔 무지성 Brute Force로 일단 갈겨봤으나 당연히 시간초과났음. ㅠ 다익스트라나 floyd-washall 같은걸로는 m회 이하를 체크하기 힘들꺼라 일단 제외함.

 

다행히 한방향으로만 진행하면 되므로 그냥 dp 돌리기로 결정함.

dp 배열 설정은 dp[i][j] - i:도시번호, j:이동횟수, value:i도시번호까지 j이동횟수로 얻은 최대 기내식 점수

처럼 해줬음.

 

그럼 이제 dp[1][1] = 0; 을 베이스로 두고 (1번에서 출발했고, 1번도 방문한 도시에 포함되니 [1][1]이 됨. 기내식은 아직 안먹었으니 value는 0)

city 번호 순서대로 살펴보면서 (25line의 반복문), arrivedCnt가 m-1일때까지(26line), edge 있는 곳으로 이동(29line)함.

결국 m이하에 대해 dp에 기입하며, '각 도시에 해당 이동횟수로 왔던 최대 기내식 점수'를 계속 계산해 나간것임.

 

그럼 최종적으로 dp[n]에 있는 배열은 n번 도시에 도착한 값 중 m번 이하만에 도착한 녀석들이고, 결국 이 값들 중 최대치가 답임.

 

소스 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02100/BOJ_2157.java