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()