글 읽기 - 두 코드의 차이점 (시간 초과 vs 맞았습니다)

lws_kahn 2년 전 0

앞 부분의 주석 처리된 코드는 시간 초과,

뒷 부분의 주석 처리되지 않은 코드는 맞았습니다를 받았습니다.

저는 보통 주석 처리된 코드의 스타일로 문제를 푸는 편인데

알고리즘은 달라진 게 없이 스타일만 바꿨을 뿐인데 통과되는 이유를 알 수 있을까요?

import sys
input = sys.stdin.readline

######### 시간 초과 #########
'''
import sys
input = sys.stdin.readline

def solve(s_row, s_col, e_row, e_col):

    dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
    
    
    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + arr[i][j]
    
    base = dp[e_row][e_col]
    delta = dp[s_row-1][e_col] + dp[e_row][s_col-1] - dp[s_row-1][s_col-1]

    return base - delta


if __name__ == "__main__":
    
    N, M = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]
    
    for _ in range(M):
        x1, y1, x2, y2 = map(int, input().split())
        print(solve(x1, y1, x2, y2))
'''



######### 맞았습니다. #########
import sys
input = sys.stdin.readline


N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (N+1) for _ in range(N+1)]

for i in range(N):
    for j in range(N):
        dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + arr[i][j]

for _ in range(M):
    
    s_row, s_col, e_row, e_col = map(int, input().split())
    
    base = dp[e_row][e_col]
    delta = dp[s_row-1][e_col] + dp[e_row][s_col-1] - dp[s_row-1][s_col-1]
    
    print(base - delta)

lws_kahn 2년 전 0

두 코드 스타일 모두 빠른 입력을 사용했습니다.

import sys
input = sys.stdin.readline

tkdgus0782 2년 전 1

윗 코드는

for i in range(N):
for j in range(N):
dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + arr[i][j]

부분이 m 번 반복되고,

아래 부분은 1번만 실행되는 차이가 있는 것 같네용

이러면 o(n2)인 아랫 코드와는 달리 윗코드는 o(n3)이 되서 시간초과가 되는게 아닌가 싶습니다,

lws_kahn 2년 전 0

저걸 놓치고 있었다니...!

다시 보니까 주석 처리된 윗 코드는 dp배열을 M번 다시 만드느라 O(M*N*N)이 되어버렸네요.

너무 단순한 실수에 부끄러워지기까지 합니다. 역시 코드 스타일의 차이가 아니었던걸로...ㅋㅋㅋㅋㅋ

감사합니다^^

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

문제

문제

출처

ICPC

두 코드의 차이점 (시간 초과 vs 맞았습니다)

lws_kahn 2년 전 0

lws_kahn 2년 전 0

tkdgus0782 2년 전 1

lws_kahn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말