[Week 2] TRIPATHCNT self review - ChaeheeKang-GitHub

[chaeheekang]

TRIPATHCNT self review

1. 해결 시도 과정

TRIANGLEPATH문제를 해결 한 후 이와 유사하게 문제를 풀려고 했지만 원하는 답이 나오지 않았습니다.
TRIANGLEPATH을 토대로 구한 dp값에서 각각의 값의 크기를 비교하여 cnt라는 새로운 배열에 개수를 기입하려고 했습니다.

2. 작성한 코드와 설명

def path(x,y):
    dp[0][0]=tri[0][0]
    #cnt의 초깃값 역시 이렇게 설정하는게 맞는지 모르겠습니다.
    cnt[0][0]=tri[0][0]
    
    for x in range(N-1):
        for y in range(x+1):
            dp[x+1][y]=max(dp[x+1][y],dp[x][y]+tri[x+1][y])
            dp[x+1][y+1]=max(dp[x+1][y+1],dp[x][y]+tri[x+1][y+1])
            
            #해당 반복문을 어디에 위치시켜야하는지 모르겠습니다.
            if dp[x+1][y]==dp[x+1][y+1]:
                cnt[x][y]=cnt[x+1][y]+cnt[x+1][y+1]
            elif dp[x+1][y]>dp[x+1][y+1]:
                cnt[x][y]=cnt[x+1][y]
            else:
                cnt[x][y]=cnt[x+1][y+1]
    print(dp)
    print(cnt)
C=int(input())
for _ in range(C):
    #삼각형의 크기
    N=int(input())
    tri=[list(map(int,input().split())) for _ in range(N)]
    dp=[[0]*N for _ in range(N)]
    cnt=[[0]*N for _ in range(N)]
    path(0,0)
    

3. 막힌 점 및 개선 사항

경로의 개수를 유추하는 cnt배열의 점화식은 이해했으나 반복문을 위치시키는 지점을 정확하게 이해하지 못했습니다.
또한 cnt의 초깃값 역시 1로 설정하는거라고 생각했는데 초깃값 설정 부분을 제대로 이해하지 못한것 같습니다.

[Queue-ri]

삼각형을 거꾸로 타고 올라간다고 생각하시면 됩니다. cnt 의 base case는 1이 맞는데요, 채희님 코드는 [0][0]만 초기화하고 계시네요. (그리고 cnt는 tri로 초기화해서도 안되겠죠, 서로 다른 목적이니까요.)

따라서 삼각형의 마지막 n-1 레벨 전체를 다 초기화해주셔야 합니다. 재귀함수로 짜면 이런 과정이 필요 없는데 반복문이기 때문에 그렇습니다.

그리고 거꾸로 타고 올라가는 것이므로 반복문도 이런식으로 설정해주시면 됩니다.

    for y in range(N - 2, -1, -1):
        for x in range(y + 1):

반복문 안에 dp는 dp[y][x]만 할당하시면 될 것 같습니다.

dp[y][x] = max(dp[y + 1][x], dp[y + 1][x + 1]) + tri[y][x]