<PART 3> Q32. 백준 1932번: 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

- bfs푼 경우

#Q32.triangle
 
n = int(input())
 
graphs = [[0]*n for _ in range(n)]
# nxn크기로 만들기
for i in range(n):
    graphs[i] = list(map(int,input().split()))
    if len(graphs[i]) != n:
        for _ in range(n-len(graphs[i])):
            graphs[i].append(0)
 
#graphs 똑같이 만들기
temp = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        temp[i][j] = graphs[i][j]
 
#대각선으로만 움직임-> 아래, 아래 오른쪽
dx = [1,1]
dy = [0,1]
 
result = 0
 
def dfs(x,y):
    global result
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
 
        # 맵안에서만 움직이기
        if nx >= 0 and nx < n and ny >= 0 and ny < n:
            temp[nx][ny] = max(temp[nx][ny], graphs[nx][ny] + temp[x][y])
            dfs(nx,ny)
    result = max(result,get_score())
    return
 
def get_score():
    score = 0
    for i in range(n):
        score = max(score,temp[n-1][i])
    return score
 
dfs(0,0)
print(result)
 
 

얕은 복사는 대입(=), [:] 슬라이싱, 객체.copy, copy.copy 가 있고
깊은 복사는 copy.deepcopy가 있습니다. 외부 라이브러리를 쓰면 안될 때가 있기 때문에 일일이 다 넣어주었다.

이렇게 하니깐 백준에서 시간초과가 나왔다. 그래서 다이나믹 프로그래밍으로 다시 풀었다.

- 다이나믹 프로그래밍

#Q32.triangle
 
n = int(input())
dp = []
 
for _ in range(n):
    dp.append(list(map(int,input().split())))
 
#다이나믹 프로그래밍으로 두 번째 줄부터 내려가면서 확인
for i in range(1,n):
    for j in range(i+1):
        #왼쪽 위에서 내려올 경우
        if j == 0:
            up_left = 0
        else:
            up_left = dp[i-1][j-1]
        if j == i:
            up_right = 0
        else:
            up_right = dp[i-1][j]
        dp[i][j] = dp[i][j] + max(up_left,up_right)
print(max(dp[n-1]))
 
 

다이나믹 프로그래밍으로 풀 때는 먼저 빈리스트를 생성 후에 점화식을 사용해야 합니다.
이때 문제에서 요구하는 정답에 대한 점화식을 빨리 생각해낼 수 있어야 하는게 관건입니다.