글 읽기 - 어떠한 부분이 시간을 많이 잡아먹는지 궁금합니다.

woojin_0727 3년 전 0

시간 초과가 나는 코드는 주석이 안되어있는 부분이고,

'''로 주석처리된 부분이 시간 초과 없이 정답으로 되는 부분입니다.

두 코드는 재귀함수, 그리고 차례대로 인구수를 구해가는 점이 같은데 왜 이렇게 다른 시간이 나오는지 궁금합니다.

pypy3로 하니 둘 다 되긴 하는데 시간이 많이 차이나요

def func(k, n):
    total=0 #호수의 인구 수가 담길 변수 total
    if n==1: #호수가 1이라면
        return 1 #그 호수의 인구로 1을 반환
    elif k==1: #층수가 1이라면
        for i in range(1, n+1): #호수만큼 반복
            total+=i #total에 1부터 호수까지 더한 값
    else: #층수가 1이 아니라면
        for i in range(1, n+1): #호수만큼 반복
            total+=func(k-1, i)
            #현재 층의 호수의 인구를 구하기 위한 과정
    return total #현재 층의 호수를 반환

T = int(input())
result = [0 for i in range(T)]

for i in range(T):
    k = int(input())
    n = int(input())
    result[i] = func(k, n)

for i in result:
    print(i)

'''
def cal_people(f, w, floor_0):
    floor_list = []
    sum = 0
    if w == 1:
        return 1
    if f == 0:
        return floor_0[w - 1]
    for j in range(w):
        sum += floor_0[j]
        floor_list.append(sum)
    return cal_people(f - 1, w, floor_list)
 
T = int(input())
floor_0 = list(range(1, 15))
for i in range(T):
    k = int(input())
    n = int(input())
    people = cal_people(k, n, floor_0)
    print(people)
'''

sanalnuri 3년 전 1

위쪽 코드는 찾으려고 하는 호실부터 좌측 하단(0층 1호실) 방향으로 순차적으로 재귀를 반복하며 값을 계산했고 이 과정에서 같은 계산을 반복하게 됩니다.

예를 들어 3층 3호실을 구하려면 다음과 같습니다. : 함수 9번 호출 중 2번 불필요한 계산 반복

3층 3호 -> 2층 1호 -> 2층 2호 -> 1층 1호 -> 1층 2호 -> 2층 3호 -> 1층 1호(반복) -> 1층 2호(반복) -> 1층 3호

아래쪽 코드의 경우 반대로 0층부터 한층 전체를 위쪽 방향으로 올라가며 계산했고 반복되는 계산이 없습니다.

예를 들어 3층 3호실을 구하려면 다음과 같습니다. : 함수 4번 호출 중 불필요한 계산 반복 없음

0층 -> 1층 -> 2층 -> 3층

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

문제

문제

출처

ICPC

어떠한 부분이 시간을 많이 잡아먹는지 궁금합니다.

woojin_0727 3년 전 0

sanalnuri 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말