[Python] 2169. 로봇조종하기(골2) / DP + 방향에 따른 배열 할당

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

2169번: 로봇 조종하기

---

2. 핵심 아이디어

 

특정 칸에 다다르는 경로는 3가지 케이스이다.

 

- 위에서 오기

- 왼쪽에서 오기

- 오른쪽에서 오기

 

예제 데이터를 기반으로 보자면 24가 적힌 칸에 다다를 수 있는 케이스는

이렇게 요약 가능하다.

- 위에서 오기 (25가 적힌 칸으로부터)

- 왼쪽에서 오기 (68이 적힌 칸으로부터)

- 오른쪽에서 오기 (-78이 적힌 칸으로부터)

 

 

그럼 천천히 각 칸에 다다르는 최대가치를 dp에 없데이트하자

 

먼저 샘플데이터와 같은 5x5 dp를 선언한다.

 

왔던 칸을 다시 못오기 때문에

첫번째 행의 경우, 왼쪽에서 오른쪽으로 진행하는 케이스밖에 없다.

그렇기 때문에 하나씩 값을 누적한 값이 그 칸에 도달하는 최대가치가 된다.

 

문제는 두번째 행부터이다.

두번째 행에서는 왼쪽 / 오른쪽을 나누어

각 좌표의 최대가치를 업데이트할 수 있다.

 

먼저 왼쪽 +위쪽 에서 오는 케이스를 생각해보자

 

현재 데이터와 dp는 다음과 같다.

[데이터]

10	25	7	8	13
68	24	-78	63	32
12	-69	100	-29	-25
-16	-22	-57	-33	99
7	-76	-11	77	15

 

[각 칸에 도달하는 최대가치]

10	35	42	50	63

 

케이스 2가지를 고려해야 하므로

왼쪽-> 오른쪽 진행되는 케이스의 최대가치를 담을 tmp1 배열을 생성해준다.

 

왼쪽-> 오른쪽으로 진행되는 케이스에서 최대가치는 다음과 같다.

tmp1 [x][y]= data[x][y] + max( dp[x-1][y](위쪽 최대가치)  or tmp1 [x][y-1](왼쪽 최대가치))

 

즉, 위에서 왔을 때와 왼쪽에서 왔을 때의 값 중 최대가치와 그 칸의 데이터 값을 합한 값이 최대값이 된다.

 

그럼 tmp1 같은 경우 이렇게 채워진다.

 

먼저 첫번째 칸의 경우, 왼쪽 최대값이 없으므로

위쪽 최대값과 데이터 값을 합한 값을 받아준다.

 

data[0]

68

24

-78

63

32

 

dp[0]

10

35

42

50

63

 

tmp1

10+68=78

 

 

계속 진행해보자

이번에는 두번째 칸이다.

data

68

24

-78

63

32

 

dp[0]

10

35

42

50

63

 

tmp1

78

78+35 = 102

 

tmp1[1] = data[1] (24) + max(위에서 온 최대값(35), 왼쪽에서 온 최대값(78))

== 24+78 = 102

=> 위쪽에서 온 최대값보다 왼쪽에서 온 최대값이 크므로 78+35

 

3번째도 같은 논리이다.

data

68

24

-78

63

32

 

dp[0]

10

35

42

50

63

 

tmp1

78

102

-78 + 102=24

 

tmp1[2] = data[2] (-78) + max(위에서 온 최대값(42), 왼쪽에서 온 최대값(102))

 

이런식으로 계속 진행되면 tmp1은 이렇게 채워진다.

78

102

24

113

145

 

 

 

---

 

이번에는 왼쪽 <-오른쪽으로 진행되는 케이스를 고려하자

이번에는 반대로 위쪽에서 온 케이스 + 오른쪽으로 온 케이스를 고려하면 된다.

 

오른쪽에서 온 케이스의 최대값을 갱신하기 위해 배열 tmp2를 만들어주고 갱신해보자

 

첫번째칸은 데이터 32와 위쪽에서 온 케이스밖에 없으므로 63을 그대로 더해준다.

 

data[0]

68

24

-78

63

32

 

dp[0]

10

35

42

50

63

 

tmp2

32+63=95

 

 

두번째 칸은 데이터 63과 max(위쪽에서 온 케이스(50) + 오른쪽에서 온 케이스(95)) 이므로

63 +95가 되어 158이 된다.

 

data[0]

68

24

-78

63

32

 

dp[0]

10

35

42

50

63

 

tmp2

63+95=158

95

 

같은 방식으로 계속 갱신하면 tmp2는 다음과 같이 채워진다.

172

104

80

158

95

 

---

이제 한 행에 대한 두가지 케이스를 비교해보자

 

tmp1(왼쪽 > 오른쪽)

78

102

24

113

145

 

tmp2 (왼쪽 < 오른쪽)

172

104

80

158

95

 

이를 기반으로 두 케이스 중 최대값을 기록하는 dp를 갱신할 수 있다.

 

---

3. 코드

#2169. 로봇 조종하기(골2)
#왼쪽, 오른쪽 아래쪽으로 이동 가능
# 탐사한 지역 가치의 합이 최대가 되도록 하는 프로그램 작성
#위에서 오는 것+ ( 왼쪽에서 오는 것 /오른쪽에서 오는 것)

import copy
n,m = map(int, input().split())
data= [list(map(int, input().split())) for _ in range(n)]

dp=[ [0]*m for _ in range(n)]
# 첫행은 누적으로 dp채워주기
dp[0]= copy.deepcopy(data[0])

for i in range(1,m):
  dp[0][i]+=dp[0][i-1]

for i in range(1, n):
  tmp1=[0]*m # 왼쪽 > 오른쪽 최대값 
  tmp2=[0]*m # 왼쪽 < 오른쪽 최대값
  
  for j in range(m):
  
    #첫번째 칸은 그냥 갱신
    if j==0: 
      tmp1[j]=data[i][j]+ dp[i-1][j] 
      tmp2[m-1-j]= data[i][m-1-j]+ dp[i-1][m-1-j]
      continue

    tmp1[j]=data[i][j]+ max(dp[i-1][j], tmp1[j-1])
    tmp2[m-1-j]= data[i][m-1-j]+ max(dp[i-1][m-1-j],tmp2[m-j])
  
  #tmp1과 tmp2 중 최대값을 dp에 갱신
  tmp=[max(tmp1[i], tmp2[i]) for i in range(m)]
  dp[i]= copy.deepcopy(tmp)

print(dp[n-1][m-1])

---

4.배운  점

다이나믹 프로그래밍은 정말 공부를 해서 극복할 수 있는 알고리즘 문제인지 의문이 들었다..

특정 관계성을 어떻게 나누고 어떻게 접근할지, 문제를 계속 풀다보면 감이 생기겠지 하지만,

정작 어려운 문제를 만났을 때 아직까진 감을 잡지 못하는 것 같다.

 

방향에 따른 갱신 문제가 나왔을 때는

이동방향에 해당하는 만큼 배열을 생성하여 , 각 값을 메모하고

모든 이동방향의 케이스 중 최대값을 뽑아내는 식의 접근방법을 배웠다.

 

참고

https://wooono.tistory.com/605