20035(이동하기 5) - 해결

이동하기 5

 

문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. (i, j)에 놓여져 있는 사탕의 개수는 Ai × 109 + Bj개이다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

 

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 100,000)

둘째 줄에는 A1, A2, ..., AN이, 셋째 줄에는 B1, B2, ..., BM이 주어진다. (0 ≤ Ai, Bj ≤ 9)

 

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

 

힌트

예제로 만들 수 있는 미로는 다음과 같은 모양이며, 편의상 (i, j)에 놓여진 사탕의 개수는 Ai, Bj로 표시했다.

0, 4	0, 1	0, 9	0, 7
7, 4	7, 1	7, 9	7, 7
1, 4	1, 1	1, 9	1, 7
7, 4	7, 1	7, 9	7, 7
6, 4	6, 1	6, 9	7, 7
7, 4	7, 1	7, 9	7, 7
6, 4	6, 1	6, 9	6, 7

 

---

행에 값이 가장 큰 영향을 주기 때문에 가장 크게 사탕을 얻기 위해서는 행의 맥스 인덱스를 찾아야한다고 생각하였다.

어차피 이동하는 칸수는 다 동일하기 때문에 그 부분을 중점으로 생각해 보았다.

그러다가 생각한 부분이 max값이 여러개 있으면 문제가 생겨서 이 부분을 생각했을때 열의 맥스 인덱스를 생각을 하여 그 부분에서 내려오면서 조금씩 큰 값을 저장하다가 다시 마지막 행 맥스 인덱스에서 다시 오른쪽을 이동하면서 사탕을 저장.

import sys
input = sys.stdin.readline

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

A = [0] + list(map(int,input().split()))
B = [0] + list(map(int,input().split()))

candys = 0
# 각 맥스값 저장
max_A = max(A)
max_B = max(B)

i = j = 1
# A 맥스 값이 유일하다면
if A.count(max_A) == 1:
    # 오른쪽으로 이동할 인덱스
    M_i = A.index(max_A)
    
    while i <= N and j <= M:
        # 사탕 저장
        candys += A[i] * (10 ** 9) + B[j]
        # 오른쪽으로 이동
        if i == M_i:
            # 다 이동하면 밑으로 이동
            if j == M:
                i += 1
                continue
            j += 1
        # 아니면 밑으로
        else:
            i += 1
# 맥스값이 여러 개일 경우
# 마지막 인덱스에서 오른쪽으로 이동
else:
    # 처음 맥스 인덱스
    M_i = A.index(max_A)
    # 마지막 맥스 인덱스
    re_A = list(reversed(A))
    M_li = N - re_A.index(max_A)
    # j 맥스 인덱스
    M_j = B.index(max_B)

    while i <= N and j <= M:
        candys += A[i] * (10 ** 9) + B[j]
        # 맥스인덱스에 오면 오른쪽을 이동
        if i == M_i:
            # j 맥스 인덱스에서 밑으로
            if j == M_j:
                i += 1
                continue
            j += 1
        # 마지막 맥스 인덱스에서 다시 오른쪽으로
        elif i == M_li:
            # 끝에 오면 밑으로
            if j == M:
                i += 1
                continue
            j += 1
        # 나머지는 밑으로
        else:
            i += 1

print(candys)