글 읽기 - 메모리 에러

fiancee10 3년 전 0

처음에는 내림차순으로 정렬하여 답을 구해냈는데 틀렸다고 하여

브루트포스 알고리즘을 적용하여 모든 정렬 경우의 수를 구한 다음 팁을 구했습니다.

그 중 최대값을 출력하게 하였는데 메모리 부족으로 실패하는데

성공하신 고수님들 도움 좀 부탁드립니다.

tips_sum_array = []
def permutation(array, start, end):
    if start == end:    
        tip_sum = 0
        for i in range(0, len(array)):
            tip = array[i]-i
            if tip > 0:
                tip_sum += tip
        tips_sum_array.append(tip_sum)
    else:
        for i in range(start, end+1):
            tempArray = list(array)

            temp = tempArray[i] 
            tempArray[i] = tempArray[start]
            tempArray[start] = temp

            permutation(tempArray, start+1, end)

# 사람의 수
n = int(input())

# 팁
tips = []
for i in range(n):
    tips.append(int(input()))

permutation(tips, 0, len(tips)-1)
print(max(tips_sum_array))

nahwasa 3년 전 1

엇.. 질문보고 풀어봤는데, 내림차순이 암만봐도 맞아보여서 내림차순으로 정렬해서 합 구하니 됬습니다?!!

뭔가 실수가 있으셨을 것 같습니다.

그리고 일단 10만명에 대한 브루트포스는 메모리 부족도 부족인데 시간도 부족할꺼라 무리로 판단됩니다.

fiancee10 3년 전 1

엇.. 다시 풀어보니까 정답뜨네요.. 뭐에 홀렸던 것일까요?!

답변 감사합니다 !!

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

문제

문제

출처

ICPC

메모리 에러

fiancee10 3년 전 0

nahwasa 3년 전 1

fiancee10 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말