https://www.acmicpc.net/problem/1149 이해 완전 탐색을 통해 해결할 수 있지만, 완전 탐색시 O(3000^3)으로 시간 초과 동적 계획법을 통해 빨강, 초록, 파랑으로 칠하는 경우 중 비용이 가장 작은 경우만 저장하는 배열을 통해 해결 구현 빨강, 초록, 파랑으로 칠할 경우 드는 비용을 저장할 dp배열 생성 N개의 집을 칠하기에 빨강, 초록, 파랑 각각 칠해온 비용을 저장할 N*3배열 생성 dp 배열은 최대의 경우를 가정했을 때 나오는 수보다 1큰 수로 저장 dp = [[1000 * 1000+1] * 3 for _ in range(N)] dp배열의 첫번째 줄은 첫 집을 빨강, 초록, 파랑을 칠할 경우의 비용으로 채움 for i in range(3): dp[0][i] = cos..

https://www.acmicpc.net/problem/1932 이해 완전 탐색을 통해 모든 경우의 수를 확인하는 방식을 사용할 수 있지만, 삼각형의 크기가 1~500 이기 때문에 완전 탐색을 할 경우 시간 초과가 날 수 있다.(2^500가지 경우의 수) 따라서 동적 계획법이용하여 시간을 줄여야 한다. 구현 동적 계획법(DP, Dynamic Programing 이하 DP)을 사용하되, 기본적인 풀이 방식이 아닌 입력을 받은 후, 입력받은 배열을 변경하는 식으로 구현 문제에 있는 크기 5의 정수 삼각형을 예시로 들어보자 i/j j=0 j=1 j=2 j=3 j=4 i=0 7 0 0 0 0 i=1 3 8 0 0 0 i=2 8 1 0 0 0 i=3 2 7 4 4 0 i=4 4 5 2 6 5 i=0일 때는 Pa..