글 읽기 - 시간 초과와 최적화...

jinhot 4년 전 0

안녕하세요. 4902 삼각형의 값 문제를 풀고 있는데요.

최적화가 잘 되지 않아 여쭙니다.

제 전략은 다음과 같습니다.

(위가 뾰족한 삼각형 구하기)

- 제일 큰 삼각형을 구합니다.

- 제일 큰 삼각형에서 좌측 빗변을 뺀 것, 우측 빗변을 뺀 것, 아래 선을 뺀 것을 다시 재귀호출 합니다.

- 이때, 빗변과 아래 선을 빼기 위해 부분합을 이용하여 즉각적으로 빼는 변의 크기를 구하게 합니다.

- 또한, visit 리스트를 만들어서 두번 이상 같은 삼각형을 연산하지 못하게 합니다.

(아래가 뾰족한 삼각형 구하기)

- 아래가 뾰족한 삼각형은 2의 배수인 위가 뾰족한 삼각형에서 2/1 크기의 삼각형을 세개 빼서 중간 부분만 남도록 합니다.

자꾸 50% 이상에서 시간 초과가 발생합니다.

배열 등을 미리 할당하거나, 입출력 함수를 바꾸어 보아도 해결이 되지 않는데, 다른 방법으로 문제를 접근해야할지 모르겠습니다...

혹시 힌트를 주실 수 있다면 부탁드리겠습니다.

import sys
sys.stdin = open("input.txt")

input = sys.stdin.readline

line_start = [0]*400

point_add = 1
point = 0

for i in range(400):
    line_start[i] = point
    point += point_add
    point_add += 2

def get_samgak_max(row_v, col_v, sum_v, n): # 경우가 세가지 있음, 오른쪽, 왼쪽, 아래쪽
    global max_v
    max_v = max(max_v, sum_v)
    if n == 2:
        return
    # 왼쪽 줄 인경우
    if not visit[n - 1 - 1][(row_v +1)][col_v + 1]:
        nsum_v = sum_v
        nsum_v -=  bubun_left[col_v][row_v - col_v + (n - 1) * 2 + 1] - bubun_left[col_v][row_v - col_v]
        cache[n - 1 - 1][(row_v + 1)][col_v + 1] = sum_v
        visit[n - 1 - 1][(row_v + 1)][col_v + 1] = True
        get_samgak_max(row_v + 1, col_v + 1, nsum_v, n - 1)
    # 오른쪽 줄인 경우
    if not visit[n - 1 - 1][(row_v + 1)][col_v]:
        nsum_v = sum_v
        nsum_v -= samgak_values[line_start[row_v] + col_v] #맨위 꼭지
        nsum_v -=  bubun_left[col_v][row_v - col_v + (n - 1) * 2 + 1] - bubun_left[col_v][row_v - col_v]
        cache[n - 1 - 1][(row_v + 1)][col_v] = sum_v
        visit[n - 1 - 1][(row_v + 1)][col_v] = True
        get_samgak_max(row_v + 1, col_v, nsum_v, n - 1)
    #아래쪽 줄 인 경우
    if not visit[n - 1 - 1][(row_v)][col_v]:
        nsum_v = sum_v
        nsum_v -= samgak_bubun[line_start[row_v + n - 1] + col_v + 1 + 2 * (n - 1) - 1] - samgak_bubun[line_start[row_v + n - 1] + col_v - 1]
        cache[n - 1 - 1][(row_v)][col_v] = sum_v
        visit[n - 1 - 1][(row_v)][col_v] = True
        get_samgak_max(row_v, col_v, nsum_v, n - 1)

#역방향일 경우??
def get_opposite(n): # 1/2 크기의 역방향 삼각형
    if big_samgak_size % 2 != 0:
        return None
    max_v = None
    for row in range(0, big_samgak_size - (n - 1)):
        for col in range(0, row + 1):
            samgak_sum = cache[n - 1][row][col]
            samgak_sum -= cache[int(n/2) - 1][row][col] + cache[int(n/2) - 1][row + int(n/2)][col] + cache[int(n/2) - 1][row + int(n/2)][col + int(n/2)]
        if max_v == None:
            max_v = samgak_sum
        else:
            max_v = max(max_v, samgak_sum)
    return max_v

count = 0
while True:
    count += 1
    input_line = input()

    if input_line == '0':
        break

    input_line = list(map(int, input_line.split()))
    big_samgak_size = input_line[0]
    samgak_values = input_line[1:]
    samgak_bubun = [0]*(len(samgak_values) + 1)
    sum_v = 0

    for i in range(len(samgak_values)):
        sum_v += samgak_values[i]
        samgak_bubun[i + 1] = sum_v

    bubun_left = [[0]*(1 + (big_samgak_size - 1 - i) * 2 + 1) for i in range(big_samgak_size)]
    for i in range(big_samgak_size):
        value = samgak_values[line_start[i] + i * 2]
        bubun_left[i][0] = 0
        bubun_left[i][1] = value
        for j in range(i + 1, big_samgak_size):
            value += samgak_values[line_start[j] + i* 2 + 1]
            bubun_left[i][(j - i)*2] = value
            value += samgak_values[line_start[j] + i* 2]
            bubun_left[i][(j - i)*2 + 1] = value

    bubun_right = [[0]*(1 + (big_samgak_size - 1 - i) * 2 + 1) for i in range(big_samgak_size)]
    for i in range(big_samgak_size):
        value = samgak_values[line_start[i] + i * 2]
        bubun_right[i][0] = 0
        bubun_right[i][1] = value
        for j in range(i + 1, big_samgak_size):
            value += samgak_values[line_start[j] + i* 2 + 1]
            bubun_right[i][(j - i)*2] = value
            value += samgak_values[line_start[j] + i* 2]
            bubun_right[i][(j - i)*2 + 1] = value

    for i in range(big_samgak_size):
        value = samgak_values[line_start[i]]
        temp = [0, value]
        for j in range(i + 1, big_samgak_size):
            value += samgak_values[line_start[j] + (j - i) * 2 - 1]
            temp.append(value)
            value += samgak_values[line_start[j] + (j - i) * 2]
            temp.append(value)
        bubun_right.append(temp)

    cache = [[[-1 for k in range(j + 1)] for j in range(big_samgak_size - i)] for i in range(big_samgak_size)]
    visit = [[[False for k in range(j + 1)] for j in range(big_samgak_size - i)] for i in range(big_samgak_size)]

    max_v = max(samgak_values)

    if big_samgak_size > 1:
        get_samgak_max(0, 0 ,samgak_bubun[-1], big_samgak_size) # 재귀적으로 호출함

        for i in range(big_samgak_size, 3, -1):
            value = get_opposite(i)
            if value != None:
                max_v = max(max_v, value)

    print('{0}. {1}'.format(count, max_v))

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

문제

문제

출처

ICPC

시간 초과와 최적화...

jinhot 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말