해결 과정 처음에는 1번째 원소 부터 작은 것을 선택해서 for 문 돌면서 최솟값을 선택하도록 했는데, 테스트케이스 5번에만 답이 안나오는 것을 발견했다. 다른 풀이가 있다는 뜻이기에 고민하다 DP임을 발견 다른 풀이를 참고했다. 직관적이다. 처음 부터 작은 원소를 선택하는 것이 아니라, 1번째를 제외한 RGB 각각에 대해 최솟값을 선택하도록 하면 된다. 나의 풀이 N = int(input()) cost = [] for _ in range(N): cost.append(list(map(int, input().split()))) dp = [[0, 0, 0] for _ in range(N)] dp[0] = cost[0] for i in range(1, N): dp[i][0] = min(dp[i-1][1], d..
해결 과정 다이나믹 프로그래밍. 마지막에 인덱스 에러는 edge case를 살펴보면 된다. 해결 과정은 다른 풀이를 참고 했다. 여기서는 마지막 계단은 꼭 밟아야 하기 때문에 이를 기준으로 케이스를 분류한다. 그래서 else문 같은 식이 나온다. 나의 풀이 N = int(input()) score = [] for _ in range(N): score.append(int(input())) dp = [0] * (N+1) if N == 1: print(score[0]) elif N == 2: print(score[0] + score[1]) else: dp[0] = score[0] dp[1] = score[0] + score[1] dp[2] = max(score[0] + score[2], score[1] + s..
해결 과정 DP 문제 하나 더 풀어보려고 본 문제. 문제는 이해가 갔으나 이걸 어떻게 DP 테이블로 풀지 감이 안와서 다른 링크를 참고했다. 먼저 그림을 그려 이해한 뒤, 코드는 보지 않고 스스로 풀어봤다. 처음에 행과 열을 바꿔서 초기화해서 런타임 에러가 났는데, 이 부분 조심. dp 테이블에 첫 행과 첫 열을 하나씩 더 두고, 0으로 초기화 해둔다. 이중 for문을 돌면서, 현재 위치의 a와 b가 같으면, dp[i-1][j-1]의 값에 + 1을 해서 넣고 다르면, dp[i-1][j] 와 dp[i][j-1] 중 더 큰 값을 넣는다. 나의 풀이 def solution(a, b): dp = [[0]*(len(b)+1) for _ in range(len(a)+1)] for i in range(1, len(a..
해결 과정 처음 봤을 때 정확하게 이해 못했다가, 각 잡고 천천히 이해해봤다. dp[N][K] ➡️ N번째 물건까지 쓰고, 수용 가능한 무게 K라고 할 때의 최대 가치. 나의 풀이 # knapsack 알고리즘 def solution(n, k, objects): dp = [[0] * (k+1) for i in range(n+1)] objs = [[0, 0]] + objects for i in range(1, n + 1): for j in range(1, k + 1): if j >= objs[i][0]: dp[i][j] = max(objs[i][1] + dp[i-1][j-objs[i][0]], dp[i-1][j]) else: dp[i][j] = dp[i-1][j] return dp[n][k] n, k = m..
코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 해결 과정 DP의 BottomUp 방식으로 해결했다. triangle을 그대로 dp로 가져왔고, 초깃값 tirangle[0][0]은 값을 따로 넣어줄 필요 없이 그대로 사용하면 되므로, 이에 대한 코드가 없다. for문은 초깃값을 제외하고 그 다음부터 탐색한다. for i in range(1, len(dp)) 나의 풀이 def solution(triangle): dp = triangle[:] for i in range(1, len(dp)): for j in range(i+1): if j == 0: dp[i][j] = dp[i-1][j] ..
