[DP🌱] 귀여운 생쥐🐁의 🧀치즈먹기! 😋

잇츠 귀여워~ 🐁🐁 

 

 

 

 

✔️문제

 

 

 

 

 

 

✔️정답

 

N, M = map(int, input().split())

table = [[0] * (N+1) for _ in range(N+1)]

for _ in range(M):
    x, y = map(int, input().split())
    table[x][y] = 1

dp = [[0] * (N+1) for _ in range(N+1)]

dp[1][1] = table[1][1]

for x in range(1, N+1):
    for y in range(1, N+1):
        dp[x][y] = max(dp[x][y-1], dp[x-1][y]) + table[x][y]

print(dp[N][N])

 

 

 

 

✔️해설

 

Point )

주어진 조건 배열과 dp배열 이용하기

dp배열에서 답 구하기

배열안에서 dp는 왼쪽값과 위의값과 같이 인접값의 최대를 구한다 !!

 

본 문제는 Bottom-Up 방식으로 문제를 풀이하였다

문제에서는 대각선 왼쪽 아래를 시작점으로, 대각선 오른쪽 위를 도착점으로 정의하였다

 

 

 

 

그러나 원래의 배열에서는

 

다음과 같이 이루어져 있고

원래의 배열은 왼쪽 위에서 [0][0] ([x][y]) 시작한다

 

※ 필자는 Python내에서 배열을 만들 때 ( 가로, 행, x )와 ( 세로, 열, y )로 지정하였고

배열을 arr라 했을때

arr[x][y]값을 요소값으로 가진다 !!

 

※ 그래서 배열을 만들때

x,y = map(int, input().split())

board = [[0] * y for _ in range(x)]
print(board)

for i in range(x):
    for j in range(y):
        print(board[i][j], end=" ")
    print()

다음과 같이 만든다

 

 

 

그렇다면 이런 질문이 있을 수 있다

 

Q) 🤔원래 문제에서는 왼쪽 아래에서 시작해서 오른쪽 위로 도착하니깐 원래 배열을 쓰는게 아니라 한번 회전시켜야 하는게 아닌가요?!

 

A) 😎하지만 문제에서 치즈 위치를 입력받을때

원래 배열 [가로 x] [세로 y] 순서대로 (내가 가로 세로 지정한 정해진 테이블에서) 입력받을 것이고 

결국 [1][1]인 시작점에서 (크기를 N+1씩 잡을것이다)

[N][N]인 도착점으로 가면서 이전 값을 사용하면서 최대의 값을 구하면서 갈 것이므로 아무 문제가 없다! 

 

해답을 구하기 위해서는

문제에서 주어진 조건의 table 배열과 dp배열이 필요하다.

 

길이가 N인 table배열을 만들고 table 배열 안에서 치즈의 위치를 입력받고

dp배열을 만든후 모든 원소값을 0으로 만든다

 

그 후 2중 반복문의 방향은 우리가 찾으려던 

 

 

대각선 왼쪽 위에서 대각선 오른쪽 아래로 가면서 최대값(왼쪽, 위쪽)에서 테이블의 치즈를 더해가면서 구한다!