백준 1149 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

처음에 문제를 이해하는데 오래 걸렸다.

 

무언가 풀리지 않을 때는, 마음이 급한 탓이다.

 

다시 차근차근 문제를 읽었고, 이해했다.

 

이 문제는 dp 문제이다.

 

어디선가 알고리즘, 코딩 테스트와 관련된 이야기를 읽다가 배운 게 있다.

 

알고리즘 문제를 풀 때는, 보통 30분에 1문제를 풀어야 한다고.

 

그래서 30분 제한을 두고 문제를 풀었지만 풀지 못했다.

 

그래서 검색해서 문제를 해결했다.

 

기본적인 문제에 접근은 같았지만, 코드 구현에서 나의 코드가 훨씬 복잡했다.

 

항상 코드를 구현하기 전 최적 방안에 대해 고민하는 시간을 가져야겠다.

 

코드

a = int(input())

dp = []

for i in range(a):

    dp.append(list(map(int,input().split())))

for i in range(1, len(dp)):

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

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

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

   

print(min(dp[a-1][0],dp[a-1][1],dp[a-1][2]))

앞으로 2차원 이상의 배열에서 dp 문제에 어떻게 접근하는지에 대해 배웠다.

 

내가 짠 코드보다 훨씬 간단하고 직관적이다...

 

갈길이 멀다.

 

배운 점

1. dp를 계산하기 위한 최적 방안이 뭔지 고민하는 시간을 반드시 가져야겠다.

 

코드 출처 : https://zidarn87.tistory.com/272

파이썬 / BOJ 백준 / 1149번 RGB 거리 - dp