글 읽기 - 문제 이해 그리고 테스트 케이스 (python 3)

smismi79 4년 전 0

아래층으로 내려올 때 이제까지 선택된 수의 합이 최대가 되는 경로

라고 했으니 다음과 같은 경로가 선택되도록 코딩했습니다

[7] --> 7

3 [8] --> 7 + 3 < 7 + 8

8 [1] 0 --> 15 +1 > 15 + 0

2 [7] 4 4 --> 16 + 7 > 16 + 4

4 [5] 2 6 5 --> 23 + 5 > 23 +2

답 : 28 이렇게 나오도록했습니다

보기에서 주어진 7 -> 3 -> 8-> 7-> 5 가 어떻게 되는지 이해가 안되네요 (예제 출력 : 30)

코드에서는 만약 왼쪽 대각선, 오른쪽 대각선의 숫자가 같은 경우 예) 3 3 3

모든 경우를 리스트로 만들어서 재귀적으로 같은 숫자(단 하나의 최대값)가 안나올때까지 만들었습니다

def main():
    import sys

    size_tri = int(sys.stdin.readline())
    pyramid =[]
    for _ in range(size_tri):
        pyramid.append([[n,int(x)] for n,x in enumerate(sys.stdin.readline().strip().split())])

    ## input 1, 1 2, 1 2 3
    '''
    pyramid = [ [[0, 1]],
                [[0, 1], [1, 2]],
                [[0, 1], [1, 2], [2, 3]]
    ]
    '''


    def same_values(index, values, depth,limit):
        '''중요한 점은 같은 값이 계속 나올 수 있다는 것이다, 예: 4만 있는 피라미드
        받는 값, 인덱스 실제값도 그냥 리스트로 받는게 안전 나중에 2의 n승까지 가능하니깐'''

        def strip_same(lists):
            temp =[]
            for x in range(len(lists)-1):
                if(lists[x]==lists[x+1]):
                    temp.append(lists[x])
            for x in temp:
                lists.remove(x)

        ln = len(index)
        index *=2; values *=2
        depth +=1
        for n, i in enumerate(index[:ln]):
            # 왼쪽 대각선
            values[n] += pyramid[depth][i][1]
            index[n] += 0
            # 오른쪽 대각선
            values[n+ln] += pyramid[depth][i+1][1]
            index[n+ln] +=1
            max_value =max(values)

        temp = [[i,v] for i,v in zip(index, values) if v==max_value]

        if(len(temp) == 1 or depth==limit):
            # print('type of temp[0]', type(temp[0]))
            return [temp[0]], depth
        strip_same(temp)
        return same_values(index,values,depth,limit)

    i=1

    curr =[x for x in pyramid[0]] # 구할 다음 층의 합 저장하는 리스트 (합이 같은 경우도 있으므로 리스트안에 리스트)
    depth =0
    size_tri -=1
    while(depth<size_tri):
        depth+=1
        for x in curr:
            # 왼쪽 대각선 합(숫자)
            a = x[1] + pyramid[depth][x[0]][1]
            a_index =  x[0]
            # 오른쪽 대각선
            b = x[1] + pyramid[depth][x[0]+1 ][1]
            b_index =  x[0] + 1
            if(a!=b):
                curr =[[a_index, a]] if a>b else [[b_index, b]]
            elif(a==b and depth<size_tri):
                two_index=[a_index,b_index]
                two_values =[a,b]
                curr, depth = same_values(two_index, two_values, depth, size_tri)


    print(curr[0][1])

if __name__=='__main__':
    main()
#

jh05013 4년 전 0

한 층 내려갈 때마다 합을 최대화시키는 게 아니라 맨 아래 층까지 내려올 때의 최종 합만 최대화시키는 문제입니다.

smismi79 4년 전 0

https://www.acmicpc.net/board/view/15978

이 글도 그렇고, 뭔소린가 싶은 부분이 이었네요 감사합니다.

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

문제

문제

출처

ICPC

문제 이해 그리고 테스트 케이스 (python 3)

smismi79 4년 전 0

jh05013 4년 전 0

smismi79 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말