글 읽기 - 11049번 Python 시간초과 PyPy 통과

park345601 4년 전 1

안녕하세요

DP연습중인데 코드가 아무리봐도 맞는거 같더라구요.. 근데 조금조금씩 수정해봐도 파이썬은 계속 시간초과가 뜹니다!

혹시나하고 pypy해봤더니 통과하더라구요 ㅠㅠ

혹시 아시는 분들은 알려주시면 감사하겠습니다!

* 참고로 반복문에서 i가 column, j와 k가 row를 나타내는데, k로 1씩 줄여가며 채우는 상황입니당 (하고보니 보통 행을 i로 했었는데 바꿔놨어서 햇갈리실까봐 적습니다)

* matrix가 각각의 행열의 행과 열의 크기를 저장하고 있고 mul이 2차 행열로 row index의 행열부터 column index 행열 까지의 곱셈의 최소를 저장하려 했습니다

import sys

N = int(sys.stdin.readline())

# matrix = [0 for _ in range(N)] # Matrix size
matrix = []
mul = [[0] * N for _ in range(N)]    
for i in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))

if N == 1:
    print(0)
else:
    for i in range(1, N):
        for j in range(i):
            k = i - j - 1
            #func(i, k)
            min_mul = 2**31 - 1
            t = 0
            
            if i - k == 1:
                mul[k][i] = matrix[k][0] * matrix[k][1] * matrix[i][1]
                continue
            while True:
                if k + t >= i:
                    break
                min_mul = min(min_mul,
                              mul[k][k + t] + mul[k + t + 1][i] + \
                              matrix[k][0] * matrix[k + t][1] * matrix[i][1])
                t += 1
            mul[k][i] = min_mul

    print(mul[0][N-1])

djm03178 4년 전 5

그냥 파이썬이 느려서 그렇습니다. Python 3로 맞은 사람이 단 한 명도 없는 문제입니다.

park345601 4년 전 0

아 질문목록만 찾아보고 멘붕왔었네요 ㅎㅎ!!

감사합니다 :)

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

문제

문제

출처

ICPC

11049번 Python 시간초과 PyPy 통과

park345601 4년 전 1

djm03178 4년 전 5

park345601 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말