BOJ(이동하기)(11048)

작성일 | In

이동하기 1048

  • 점화식은 세웠는데, 구현을 못했다.

  • 보기 쉽게 한 배열에서 처리하려고 하지말고, 그냥 dp배열을 하나 새로 만들자.

  • 물론 arr 하나만 써서 풀 수 있긴 하지만, 좀 헷갈리는 것 같다.

구현을 못한 이유

  • 구현을 못한 가장 큰 이유는 입력을 받을 때, 이차원 리스트 좌 우에 0을 추가해줘야 한다는 점이다.
  • a = [[0]*(m+1)] + [[0]+list(map(int,input().split())) for _ in range(n)]
  • 이걸 못해서 틀렸다.

구현 1.

  • (i,j)에 올 수 있는 것의 점화식을 세움
for i in range(1, n+1):
    for j in range(1, m+1):
        d[i][j] = max(d[i-1][j],d[i][j-1],d[i-1][j-1])+a[i][j]

구현 2.

  • (i,j)로 갈 수 있는 것의 점화식을 세움
d[1][1] = a[1][1]
for i in range(1, n+1):
    for j in range(1, m+1):
        if j+1 <= m and d[i][j+1] < d[i][j] + a[i][j+1]:
            d[i][j+1] = d[i][j] + a[i][j+1]
        if i+1 <= n and d[i+1][j] < d[i][j] + a[i+1][j]:
            d[i+1][j] = d[i][j] + a[i+1][j]
        if i+1 <= n and j+1 <= m and d[i+1][j+1] < d[i][j] + a[i+1][j+1]:
            d[i+1][j+1] = d[i][j] + a[i+1][j+1]

구현 3.

  • 어차피 값이 모두 0 이상이기 때문에, 대각선을 갈 필요가 없이 가로와 세로만 가면 된다
n, m = map(int, input().split())
a = [[0]*(m+1)] + [[0]+list(map(int, input().split())) for _ in range(n)]
d = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        d[i][j] = max(d[i-1][j], d[i][j-1])+a[i][j]
print(d[n][m])

구현 4

  • 재귀함수를 이용한 구현
  • 식이 달라지는 것도 아니고, 구현 방식만 달라진다.
  • Bottom-up 소스를 top down으로 바꿔야 한다.
  • Bottom-up에서는 작은 것에서부터 채워야 하므로 for문이 가장 중요

  • top down에서는 채우는 순서가 중요하지 않다. 답을 구한 적이 없는 칸이라면, 값을 구해서 리턴, 값을 구한 적이 있으면 그냥 리턴

  • bottom-up에서는 작은 문제가 풀렸다는 가정을 했기에, 함수의 호출의 호출로 그 부분을 바꿔줘야 한다.
  • 또한 범위를 정해줘야 한다.
  • 이 경우 답이 음수인 경우가 없기 때문에 -1로 초기화하고 문제를 풀어야 한다.
import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
a = [[0]*(m+1)] + [[0]+list(map(int,input().split())) for _ in range(n)]
d = [[-1]*(m+1) for _ in range(n+1)]
def go(i,j):
    if i < 1 or j < 1:
        return 0
    if d[i][j] >= 0:
        return d[i][j]
    d[i][j] = max(go(i-1,j),go(i,j-1))+a[i][j]
    return d[i][j]
print(go(n,m))

방법 5 식을 채우는 순서를 다르게

  • 점화식을 (i,j )에서 시작했을 때, 가져올 수 있는 최대 사탕개수로 바꿔서 풀 수 있다.
import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
a = [[0]*(m+1)] + [[0]+list(map(int,input().split())) for _ in range(n)]
d = [[-1]*(m+1) for _ in range(n+1)]
def go(i,j):
    if i > n or j > m:
        return 0
    if d[i][j] >= 0:
        return d[i][j]
    d[i][j] = max(go(i+1,j),go(i,j+1))+a[i][j]
    return d[i][j]
print(go(1,1))

참고자료 codeplus

0%