동적계획법

백준 11049 (행렬 곱셈 순서, DP)

처음에 보고 먼소린가 했는데 행렬의 곱셈이 이루어진 후의 연산 비용을 계산해보는 문제이다. 따라서 최소값을 구하면 된다. 그럼 식을 세워야 한다. 저번에 풀었던 11066문제와 비슷하다. 양옆으로 연산을 하기 때문에 잘 쪼개서 계산하면 된다. 그래서 일반항으로 나타내면 아래와 같다. 아주 다행인건 최적화 따위를 안해도 된다는 것이다. 여기서 팁은 최솟값이 적어도 2^31-1보다 작아야한다는 것이다. 따라서 이부분을 놓치지 않고 코딩으로 바꾸어 주면 아래와 같다. n = int(input()) p = [] for i in range(n): p.append(tuple(map(int, input().split()))) D = [[0 for i in range(n)] for i in range(n)] # 연산시..

백준 1932 풀이 (동적 계획법)

저번 문제가 1149 였는데 이때 굉장히 신기한 방식을 사용했다. 재귀로 풀어야할것 같은 최댓값 최소값을 구할때 뒤로 더해서 누적값을 만들어 주면 모든 경우를 염두하여 푸는 방식이 된다. 만약 이 삼각형의 각 층별 총합을 구하여 최댓값을 구하려면 재귀함수를 써야한다. 문제는 이러한 경우 재귀함수의 호출 갯수가 비약적으로 많아지게 된다는 것이다. 그래서 저번 1149 문제에서는 누적값을 만들어서 최솟값을 구했다. 이번에도 비슷한 방식으로 누적값을 만들어서 최댓값을 구하면된다. 아래에서 부터 어떤 선택을 할때 최댓값이 되는지 구하면서 올라가면 1층의 7은 최댓값으로 값이 변경된다. 코드는 굉장히 간단해진다. n = int(input()) tmp = [] for _ in range(n): tmp.append(..