글 읽기 - 파이썬 시간초과 질문

kevin991020 1년 전 0

음...제가 PYTHON3로 제출하니 시간초과가 떠서

그대로 C++코드로 옮겨적었더니 맞았습니다..

혹시 정상인가요..?

PYPY3로 하고싶었지만 RECURSION 깊이제한때문에 PYTHON3를 사용했습니다.

import sys
from collections import deque
import bisect
import random
sys.setrecursionlimit(10**9)
n,m = list(map(int,sys.stdin.readline().split()))
arr = [[0 for i in range(m)] for j in range(n)]
dp = [[[-1 for k in range(3)] for i in range(m)] for j in range(n)]
visited = [[0 for i in range(m)] for j in range(n)]
dx = [0,1,0]
dy = [-1,0,1]
for i in range(n):
    arr[i] = list(map(int,sys.stdin.readline().split()))
def isOk(x,y):
    if x < 0 or x >= n: return False
    if y < 0 or y >= m: return False
    return True

def func(curx,cury,dir):# 0:왼쪽에서 1 : 위쪽에서 2 : 오른쪽에서
    if curx == n-1 and cury == m-1:
        return arr[curx][cury]
    if dp[curx][cury][dir] != -1: 
        return dp[curx][cury][dir]
    dp[curx][cury][dir] = -1111111111
    for i in range(3):
        nextx = curx + dx[i]
        nexty = cury + dy[i]
        if not isOk(nextx,nexty): continue
        if visited[nextx][nexty] == 1: continue
        visited[nextx][nexty] = 1
        dp[curx][cury][dir] = max(func(nextx,nexty,i),dp[curx][cury][dir])
        visited[nextx][nexty] = 0
    dp[curx][cury][dir] += arr[curx][cury]
    return dp[curx][cury][dir]

visited[0][0] = 1

print(func(0,0,0))

----------------------------------------------------------------------------------------

#include <cstdio>
#include <vector>
#include <iostream>
#include <memory.h>
using namespace std;
int n,m;
int arr[1001][1001];
int visited[1001][1001];
int dp[1001][1001][3];
int dx[] = {0,1,0};
int dy[] = {-1,0,1};
int isOk(int x,int y){
   if (x < 0 || x>= n) return false;
   if (y < 0 || y>= m) return false;
   return true;
}
int func(int curx,int cury, int dir){
   if (curx == n-1 and cury == m-1) return arr[curx][cury];
   if (dp[curx][cury][dir] != -1) return dp[curx][cury][dir];
   int& ret = dp[curx][cury][dir];
   ret = -1111111111;
   for(int i = 0; i < 3; i++){
      int nextx = curx + dx[i];
      int nexty = cury + dy[i];
      if (!isOk(nextx,nexty)) continue;
      if (visited[nextx][nexty] == 1) continue;
      visited[nextx][nexty] = 1;
      ret = max(ret,func(nextx,nexty,i));
      visited[nextx][nexty] = 0;
   }
   ret += arr[curx][cury];
   return ret;
}
int main(){
   cin.tie(0); cin.sync_with_stdio(0);cout.tie(0);
   cin>>n>>m;
   memset(visited,0,sizeof(visited));
   memset(dp,-1,sizeof(dp));
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         cin>>arr[i][j];
      }
   }
   visited[0][0] = 1;
   cout<<func(0,0,0);
}

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

문제

문제

출처

ICPC

파이썬 시간초과 질문

kevin991020 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말