[2020 카카오 기출] 경주로 건설(JAVA)

programmers.co.kr/learn/courses/30/lessons/67259

---

DP 문제입니다.

 

저는 dp 상태를 아래와 같이 정의했습니다.

dp[dir][y][x]: board[y][x]에 경주로를 놓았고 현재 진행중인 방향은 dir인 상태입니다.

dir은 UP LEFT DOWN RIGHT 4가지 상태중 하나를 가지게 됩니다.

 

경주로를 놓기 위해 새로운 칸을 탐색할 때 총 3방향을 탐색할 수 있습니다.

 

1. 온 방향 그대로 진행

2. 온 방향과 90도를 이루는 방향 진행

 

그리고 그 때 마다 금액을 쌓아주면 됩니다.

 

단 제가 구하는 방식의 경우 코너 도로를 놓을 때 100원씩이 누락됩니다.

 

예를 들어,

ㅣ

ㄴ ㅡ 

 

이렇게 3개의 도로를 놓는다고 할 때 총 700원이 들어야 하지만,

제가 구현한 방식의 경우는 600원만 듭니다. 그러므로 하나의 코너 도로를 놓을 때마다

500원이 아니라 600원을 카운트함으로써 이 부분을 해결했습니다. 

---

코드: github.com/cotchan/algorithm/blob/main/java/PROGRAMMERS/PG67259.java