글 읽기 - 20035번 문제 어디가 문제일까요..?

joyh1021 3년 전 0

구글링을 해봐도 정답 레퍼런스가 찾기가 힘드네요... Python 코드로 답을 공개하신 분들도 없으시구...

어떤 아이디어를 추가해서 문제를 풀어야할까요.? 제 소스코드를 실행시키면 시간이 너무 오래걸리네용... 고수님들 도와주세유..

# N이 행, M이 열
import sys
N, M = map(int, sys.stdin.readline().split())
N_nums = list(map(int, sys.stdin.readline().split()))
M_nums = list(map(int, sys.stdin.readline().split()))

matrix = [[[N_nums[n],M_nums[m]] for m in range(M)] for n in range(N)]
n, m = 0, 0
# 처음에 0,0 좌표의 사탕 개수 계산
count = matrix[n][m][0] * 1e9 + matrix[n][m][1]

while True:
    # A에 있는 개수가 많은 쪽으로 무조건 가야 함!
    right = matrix[n][m+1][0]
    under = matrix[n+1][m][0]
    if right > under:
        count += right * 1e9 + matrix[n][m+1][1]
    else:
        count += under * 1e9 + matrix[n+1][m][1]
    # 만약 오른쪽으로 계속 가다가 벽에 부딪쳤다!
    if m == M-1:
        # (N, M)에 도착한 경우
        if n == N-1:
            print(count)
            break
        # 아래로 쭉 가기!
        else:
            while n != N-1:
                count += under * 1e9 + matrix[n+1][m][1]
            print(count)
            break
    # 만약 아래쪽으로 계속 가다가 벽에 부딪쳤다!
    if n == N-1:
        # (N, M)에 도착한 경우
        if m == M-1:
            print(count)
            break
        # 오른쪽으로 쭉 가기!
        else:
            while m != M-1:
                count += right * 1e9 + matrix[n][m+1][1]
            print(count)
            break

azberjibiou 3년 전 0

N하고 M범위가 10^5인데 NM크기의 리스트는 10^10이니까 메모리가 터지는거일거에요

보통 10^8 스케일 근처에서만 뭔가를 할 수 있어요

이 문제는 직접 맵을 탐색하는 문제가 아니라 적당히 뭔가 잘 띵킹을 해보면 슥삭하고 풀리는 문제에요

화이팅!

joyh1021 3년 전 0

해보겠습니다! 응원 감사합니다 !

joyh1021 3년 전 0

azberjibiou 님..! 보실지 모르겠지만.. 제가 다시 풀고 난 다음 질문을 재차 올렸는데 확인 부탁드려도 될까요!!! ㅜㅜ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

20035번 문제 어디가 문제일까요..?

joyh1021 3년 전 0

azberjibiou 3년 전 0

joyh1021 3년 전 0

joyh1021 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말