Leta Learns

문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 아 디피 어렵다!!!!!!! 어떻게 풀어야 하나 감이 안 잡혔는데 시간제한이 0.5초라서 이중 for문은 절대 쓰면 안 됐고,, 혹시 DP인가... 하면서 알고리즘 분류를 확인했더니 DP가 맞았다. 처음에 for문을 0번 인덱스부터 돌려서 좀 헤맸다. 1번 인덱스부터 돌리면 바로 전 집의 최솟값과 자신의 값을 더해서 값을 갱신해주면 된다. import sys input ..

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP 오랜만에 푸는 거라 정신 못 차렸다. 어떻게 풀어야 할 지 감이 안 잡혀서 알고리즘 분류 확인하고 디피 문제라는 걸 확인한 후에 풀었다. 디피 연습을 좀 해야할 것 같다. 간단한 코드 설명은 주석으로 적어놓았다. import sys input = sys.stdin.readline n= int(input()) dp = [0 for _ in range(n+1)] for i in range(2, n+1): dp[i] = dp[i-1] + 1 #일단 1은 무조건 빼놓고 (연산 3) if i % 3 == 0:..

#subproblem을 그대로 합치면 되는 DP - 피보나치 수 https://www.codetree.ai/missions/2/concepts/6/problems/fibonacci-number/description 코드트리 삼성 SW역량테스트, 코드트리와 함께 www.codetree.ai n = int(input()) def fibonacci(n): if n = coin[j-1]: dp[i] = min(dp[i], dp[i - coin[j-1]] + 1) if dp[m] == float('inf'): print(-1) else: print(dp[m]) 아 이 문제는 너무 어려웠다.. 해설 다시 보면서 공부 더 해야 할 것 같다... DP 점화식 고안하는 거 너무 어렵다.. 전에는 그래프가 더 어렵다고 생..

1. Tree DP Tree : cycle이 없는 그래프 (서로 다른 두 노드를 잇는 길이 하나) => 그래프처럼 DP 기법 적용 가능 트리에서 DP는 서브트리에서 구한 해를 이용하여 전체 트리의 해를 구하는 방식으로 진행된다. 트리는 비선형 구조이므로 DP를 하기 전에 탐색 순서를 미리 정해주는 것이 일반적. => 보통 탐색 순서는 DFS를 돌면서 나오는 트리를 기준으로 함. 기본적으로 Top-down 방식으로 코드 작성. => 보통의 DFS처럼 leaf 노드까지 순회하고, leaf 노드의 값을 알아낸 뒤 상위 노드의 값들을 알아내는 방식. Tree DP 예제 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 ..