from palette import colorful_colors

https://www.acmicpc.net/problem/1149언어: C++, 시간: 0ms 접근방법대표적인 dp를 이용하는 문제. 먼저 입력을 행이 N이고 열이 3인 맵에 담고 난 후, 0행부터 N-1행까지 dp로 최솟값의 합을 저장한다: i 번째 행의 R칸에는 i-1번째의 G칸과 B칸 중 min을 저장한다.i 번째 행의 G칸에는 i-1번째의 R칸과 B칸 중 min을 저장한다.i 번째 행의 R칸에는 i-1번째의 R칸과 G칸 중 min을 저장한다....이런식으로 저장하게 되면, i번째 행의 각 열에는 i번째 집에 해당 색깔로 색칠했을때 + 그 이전 행들에 색칠하는 총 최소 비용이 저장된다.dp를 다 구하고 난 후, 정답은 N-1 행의 각 열에 담긴 숫자 중 최솟값이다. 1000 x 1000은 int 범..

import sys input = sys.stdin.readline # 입력받기 N = int(input()) for i in range(N): d.append(list(map(int, input().split()))) # 초기값 if N > 2: d[1][0] = d[0][0] + d[1][0] d[1][1] = d[0][0] + d[1][1] # 메모이제이션 하면서 계산 for i in range(2, N): for j in range(0, i+1): if j == 0: d[i][j] = d[i - 1][0] + d[i][j] elif j == i: d[i][j] = d[i - 1][j - 1] + d[i][j] else: d[i][j] = max(d[i-1][j-1] , d[i-1][j]) + d[..

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈 메모리 공간을 더 사용하여 연산 속도를 증가시킬 수 있는 방법. ex) 점화식을 이용해 풀기 2가지 방법(top down, bottom up)이 있다. 예시: 피보나치 함수 # 피보나치 함수를 재귀로 구현할때 def pibo(x): if x == 1 or x == 2: return 1 else: return pibo(x-1) + pibo(x-2) print(pibo(4)) 이렇게 단순 재귀로 작성하면 n이 커질 수록 시간복잡도가 기하급수적으로 늘어난다. O(2^N) 따라서 dp를 이용한다. dp를 사용할 수 있는 경우: 1. 큰 문제를 작은 문제로 나눌 수 있다 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하..