[백준] 1932번 정수 삼각형 (Python)

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

1932번: 정수 삼각형

---

풀이과정

①문제 들여다보기

이건 RGB 문제랑 유사한 것 같음. 다만, list의 len이 매번 달라져서 이 부분을 좀 신경써줘야 한다고 생각함.

 

②아이디어 열기

일단 range를 거의 쌩까고 코드를 짜봄

무지성으로 짠 코드

역시 IndexError가 떴다.

 심지어 print(max(dp[N-1])) 로 해줘야함! 굉장히 멍청한 실수였다.

 

edge를 고려해서 짠 코드

list의 첫 번째와 마지막 부분일 때 예외적으로 dp[i-1][j-1]과 dp[i-1][j]를 비교할 수 없기에 따로 처리를 해주었다.

근데 이 코드가 과연? 시간 초과가 나지 않을까요.. 2중 for문이기에 뭔가 많이 날 것 같았다.

그치만 나지 않았다! 왜냐면, 이중 for문으로 비교를 할 때 그런거지 단순 그냥 탐색 용도에 불과해서 그런거같음. 아니라면 다음에 수정해보도록 하겠다!

 

 

③최종 코드

N = int(input())
dp = [list(map(int,input().split())) for _ in range(N)]

if N == 1:
    print(dp[0][0])

else:
    for i in range(2):
        dp[1][i] = dp[1][i] + dp[0][0]

    for i in range(2,N):
        for j in range(i+1):
            if j == i:
                dp[i][j] = dp[i-1][j-1] + dp[i][j]
            elif j == 0:
                dp[i][j] = dp[i-1][j] + dp[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + dp[i][j]
    print(max(dp[N-1]))