글 읽기 - pypy3는 통과했는데.....python3는 통과가 안되네요.[시간초과]

blutics 5년 전 0

음........어디서 더 줄일 수 있을까요???

import sys
input=sys.stdin.readline
x=[[*map(int,input().split())]for i in range(9)]
y=[[x[i][j]for i in range(9)]for j in range(9)]
z=[[x[i][j]for i in range(3*u,3*u+3) for j in range(3*p,3*p+3)]for u in [0,1,2] for p in [0,1,2]]
m=[]
for i in range(9):
    for j in range(9):
        if x[i][j]==0:
            m+=(i,j),
def solve(n=0):
    if n==len(m):
        return 1
    i,j=m[n]
    k=possibilities(i,j)
    for w in k:
        x[i][j]=w
        y[j][i]=w
        z[3*(i//3)+(j//3)][3*(i%3)+(j%3)]=w
        if solve(n+1):return 1
        x[i][j]=0
        y[j][i]=0
        z[3*(i//3)+(j//3)][3*(i%3)+(j%3)]=0
    return 0
def possibilities(row,col):
    return [*filter(lambda t:not t in x[row]+y[col]+z[3*(row//3)+(col//3)],range(1,10))]
solve()
for i in x:print(*i)

djm03178 5년 전 1

채점 기록을 보면 Python 3로 통과한 코드는 거의 없습니다. 백트래킹을 매우 효율적으로 구현하거나, 아니면 다른 방법을 써야 될 듯 합니다.

cubelover 님의 코드를 보면 https://www.acmicpc.net/source... 와 https://www.acmicpc.net/source... 는 동일한 코드임에도 불구하고 PyPy3와 Python3의 수행 시간이 매우 크게 다른 것을 볼 수 있습니다.

blutics 5년 전 0

저도 효율적으로 구현한다고 했는데.....1000ms정도를 더 당겨야하는데 뭘로 당겨야할지....ㅎㅎ

djm03178 5년 전 4

"Part of the contest is knowing which tool to use for which job, just as in everyday software engineering." -jh05013

jh05013 5년 전 2

저 말고 구글이 한 말입니다.

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

문제

문제

출처

ICPC

pypy3는 통과했는데.....python3는 통과가 안되네요.[시간초과]

blutics 5년 전 0

djm03178 5년 전 1

blutics 5년 전 0

djm03178 5년 전 4

jh05013 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말