글 읽기 - 요세푸스2 메모리초과를 어떻게 해결해야 할까요

cclang 2년 전 0

이문제 외에도 파이썬으로 메모리초과가 뜰때가 상당히 많았는데
어떻게 해결해야 하는지 알려주시면 감사하겠습니다.

from math import *
import sys

N, K = map(int, input().split())
num = [1 for i in range(N)]
segtree = [0 for i in range(1 << (ceil(log2(N)) + 1))]


def init_segtree(st, ed, index):
    if st == ed:
        segtree[index] = num[st]
        return segtree[index]
    md = (st + ed) // 2
    segtree[index] = init_segtree(st, md, index * 2 + 1) + \
                     init_segtree(md + 1, ed, index * 2 + 2)
    return segtree[index]


def del_segtree(pos, st, ed, index):
    if st == pos and st == ed:
        segtree[index] = 0
        return segtree[index]
    if pos < st or ed < pos:
        return segtree[index]
    md = (st + ed) // 2
    segtree[index] = del_segtree(pos, st, md, index * 2 + 1) + \
                     del_segtree(pos, md + 1, ed, index * 2 + 2)
    return segtree[index]


def get_sum(lf, ri, st, ed, index):
    if ed < lf or ri < st:
        return 0
    if lf <= st and ed <= ri:
        return segtree[index]
    return get_sum(lf, ri, st, (st + ed) // 2, index * 2 + 1) + \
           get_sum(lf, ri, (st + ed) // 2 + 1, ed, index * 2 + 2)


def get_next_pos(movepos, st, ed, index):
    if st == ed:
        return st
    if segtree[index * 2 + 1] < movepos:
        return get_next_pos(movepos - segtree[index * 2 + 1], (st + ed) // 2 + 1, ed, index * 2 + 2)
    return get_next_pos(movepos, st, (st + ed) // 2, index * 2 + 1)


sys.stdout.write("<")
present_pos = 0
init_segtree(0, N - 1, 0)
while segtree[0] > 0:
    move_pos = K
    if present_pos != 0:
        move_pos += get_sum(0, present_pos - 1, 0, N - 1, 0)
    move_pos %= segtree[0]
    if move_pos == 0:
        move_pos = segtree[0]
    present_pos = get_next_pos(move_pos, 0, N - 1, 0)
    del_segtree(present_pos, 0, N - 1, 0)
    if segtree[0] == 0:
        sys.stdout.write(f"{present_pos + 1}>")
    else:
        sys.stdout.write(f"{present_pos + 1}, ")

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

문제

문제

출처

ICPC

요세푸스2 메모리초과를 어떻게 해결해야 할까요

cclang 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말