[백준][DP] 4883. 삼각 그래프

4883. 삼각 그래프

4883번: 삼각 그래프

 

• 내 풀이- 첫시도 : 실패
  • 전행에서 계산한 것만 고려
  • 화살표를 보면 옆에서 오는것도 고려해줘야함

cnt = 0
while True:
    n = int(input())
    if n == 0:
        break
    cnt += 1

    graph = []
    for i in range(n):
        graph.append(list(map(int, input().split())))

    dp = [[0 for _ in range(3)] for _ in range(n)]
    dp[0] = [graph[0][1]]*3

    for i in range(1, n):
        dp[i][0] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + graph[i][0]

        dp[i][1] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + graph[i][1]

        dp[i][2] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + graph[i][2]

    print(cnt, ". ", dp[n-1][1])

 

 

• 재시도
  • 0행에서 dp[0][2]는 min(graph[0][1], graph[0][1]+graph[0][2])
  • 열이 1일땐 0에서 오는 방향성, 2일땐 1에서 오는 방향성 고려
  • 화살표가 오는것만 확인

반례
3
1 1 1
1 1 1
-1 1 1
0
답: 2

 

cnt = 0
while True:
    n = int(input())
    if n == 0:
        break
    cnt += 1

    graph = []
    for i in range(n):
        graph.append(list(map(int, input().split())))

    dp = [[0 for _ in range(3)] for _ in range(n)]
    dp[0] = [graph[0][1], graph[0][1], min(
        graph[0][1], graph[0][1]+graph[0][2])]

    for i in range(1, n):
        dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + graph[i][0]

        dp[i][1] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i][0]) + graph[i][1]

        dp[i][2] = min(dp[i-1][1], dp[i-1][2], dp[i][1]) + graph[i][2]

    print(f'{cnt}. {dp[n-1][1]}')