dynamic programming을 이용한 알고리즘 문제풀이
문제
N x M 크기 벌집은 육각형이 가로 N칸이 한 줄로 이어져 있고, 이 줄이 모두 M 줄 있는 형태이다.
예를 들어, 아래 그림은 4 x 3 크기 벌집이다.
벌집의 각 칸마다 (x, y) 형태로 좌표값이 주어지는데, 이는 위에서 x번째 줄, 왼쪽으로부터 y번째 칸에 있다는 뜻이다. 가장 왼쪽 위 칸은 (1, 1)이고, 가장 오른쪽 아래의 칸은 (M, N)이다. 각 칸마다 꿀이 들어있고, 벌이 해당하는 칸을 방문하면 이 꿀을 먹을 수 있다.
처음 벌은 (1, 1)에 있다. 매번 벌은 자신이 있는 육각형의 바로 오른쪽에 인접한 칸, 또는 대각선으로 오른쪽 아래에 인접한 칸으로 이동할 수 있다.
예를 들면 (2, 1)에 있는 벌은 (2, 2) 또는 (3, 2)로 이동할 수 있다. 벌이 (M, N)에 도착하면 멈춘다.
벌집의 크기와 각 칸마다 꿀의 양이 주어졌을 때 벌이 먹을 수 있는 꿀의 최대값을 구하는 프로그램을 작성하시오.
입력
표준입력으로 입력을 받는다. 첫 줄에는 두 자연수 N M이 사이에 공백을 두고 주어진다.
N은 2 이상 1000 이하, M은 2 이상 1000과 2 * N 중 작은 쪽 이하이다.
다음 줄부터 총 M줄에 각 칸에 들어있는 꿀의 정보가 주어진다. 한 줄에는 N개의 정수가 사이에 공백을 두고 주어진다.
이 값들은 모두 0 이상 100 이하이다.
출력
표준출력으로 출력한다. 한 줄에 벌이 먹을 수 있는 꿀의 최댓값을 출력한다.
예제 입력 1
4 3
1 0 0 0
2 1 0 0
1 0 0 0
예제 출력 1
4
다음 그림과 같이 이루어 진다.
문제 풀이
honey라는 2차원 리스트에 입력해 주는 꿀의 정보를 입력받자.
honey [m-1][n-1] -> 이건 (n, m) 칸에 위치한 꿀의 정보이다. 위 예시에서 honey [0][0] = 1 이 되겠다.
이때 (0,0)에서 (n, m)까지 가면서 먹은 꿀의 누적값을 score라는 이차원 리스트에 기록해 보자. 이 이차원 리스트는 honey처럼 M*N 짜리가 아닌 (M+1)*(N+1) 짜리로 할 것이다. 이유는 계산상의 편의 때문인데 x 좌표와 y좌표가 0인 인덱스는 0으로 비워두는 게 계산하기 편할 것이기 때문이다.
score [M][N]은 (N, M)까지 오는데 내가 먹은 꿀의 최댓값이 될것이고, 그러면 내가 원하는 답은 score[M][N]이 될것이다. 그럼 이 score[M][N]은 어떻게 구하냐? (1,1) 부터 윗줄부터 아랫줄로 내려가면서, 또 같은 줄에서는 왼쪽에서 오른쪽으로 진행하면서 먹은 꿀의 최댓값을 구해주며 기록하면 된다.
(N,M)까지 오는데 먹은 꿀의 최댓값을 구하는 법은 일반적으로 말하면 (N, M)으로 올 수 있는 왼쪽 블록과 왼쪽 위 대각선 블록의 score중에 최댓값과 (N,M)의 honey값이 될 것이다.
여기서 하나 고려해야 할 점은 이쁜 격자형이 아니라 벌집 모양이므로 y좌표가 홀수일 때와 짝수일 때 (N,M)으로 올 수 있는 좌표의 값이 달라지므로 이를 고려하여 코드를 짜야한다.
또한, (1,1)에서 (N, M)으로 가는 길에는 우리가 입력한 값 중에 최단 거리로 가게 된다면 들를 수 없는 점이 존재한다. 왼쪽 밑 좌표들과 오른쪽 위 좌표들의 일부가 포함될 것인데, 오른쪽 위 좌표들은 위에 내가 말한 대로 계산한다면 계산에 포함될 일이 없으므로 고려하지 않고 왼쪽 밑의 좌표들만 고려해 보자.
1,2 번째 줄에는 빼야 할 점이 0개, 3,4 번째 줄에는 빼야할 점이 1개, 5,6 번째 줄에는 빼야할 점이 2개 ... 이런 규칙으로 빼야할 점이 생긴다. 이때 index값들은 y좌표에서 -1 된 값이므로 y index // 2 하게 된다면 해당 값만큼 지워주면 된다.
이후 위에서부터 순서대로 계산을 하게 된다면 (N, M)까지 해당 좌표까지의 먹을 수 있는 꿀의 최댓값을 기록하게 된다. 그러니 이후에는 출력만 하면 끝이다!
import sys
def main():
N,M = map(int, sys.stdin.readline().split())
score = [[0 for _ in range(N+1)] for _ in range(M+1)]
honey = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]
#왼쪽 밑의 점 중 지나가지 않는 점은 계산되지 않도록 지워준다
for i in range(M):
for j in range(i//2):
honey[i][j] = 0
#왼쪽 타일과 왼쪽 위 타일 중 최댓값과 해당 타일의 꿀 갯수를 더해 score에 저장한다.
#y좌표가 홀수일 때와 y좌표가 짝수일 때 index관계가 다르므로 나눠서 계산하자.
for i in range(1,M+1):
for j in range(1,N+1):
if i%2 == 1:
score[i][j] = max(score[i][j-1], score[i-1][j-1]) + honey[i-1][j-1]
else:
score[i][j] = max(score[i][j-1], score[i-1][j]) + honey[i-1][j-1]
print(score[M][N])
if __name__=="__main__":
main()