선호:하다

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net n = int(input()) data = [0] * 300 for i in range(n): data[i] = int(input()) dp = [0] * 300 dp[0] = data[0] dp[1] = data[0] + data[1] dp[2] = max(data[0] + data[2], data[1] + data[2]) for i in range(3, n): dp[i] = max(dp[i - 2] + d..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net import sys n = int(sys.stdin.readline()) graph = [] for _ in range(n): data = list(map(int, sys.stdin.readline().rstrip().split())) graph.append(data) dp = [[0] * 3 for _ in range(n)] dp[0] = graph[0] for i in r..

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net import sys n = int(sys.stdin.readline()) data = list(map(int, sys.stdin.readline().rstrip().split())) dp = [1] * n for i in range(1, n): for j in range(0, i): if data[i] < data[j]: dp[i] = max(dp[i], dp[j] + 1) print(..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net n = int(input()) data = [] for i in range(n): time, benefit = map(int, input().rstrip().split()) data.append((time, benefit)) dp = [0] * (n + 1) max_value = 0 for i in range(n - 1, -1, -1): if i + data[i][0] n: continue dp[i] = data[i][1] for j in range(i): if data[j][0] + j > i: continue dp[i] = max..

https://youtu.be/5Lu34WIx2Us 이 문제의 해설 영상이다. 문제 n x m 크기의 금광이 있다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작하는데 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 테스트 케이스 T가 입력된다. (1

https://youtu.be/5Lu34WIx2Us 이 문제의 해설 영상이다. 문제 N가지 종류의 화폐 중에서 화폐의 개수를 최소한으로 이용해 그 가치의 합이 M원이 되도록 한다. (화폐 개수는 무제한이며 순서가 달라도 같은 걸로 친다) 입력 조건 첫째 줄에 N, M이 주어진다. (1

https://youtu.be/5Lu34WIx2Us 이 문제의 해설 영상이다. 문제 개미 전사는 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. {1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 ..

다이나믹 프로그래밍(Dynamic Programming) 동적 계획법이라고도 불리는 다이나믹 프로그래밍은 메모리를 약간 더 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 다이나믹 프로그래밍에서는 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다. 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다. 최적 부분 구조(Optimal Substructure)- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 문제 중복되는 부분 문제(Overlapping Subproblem)- 동일한 작은 문제를 반복적으로 해결해..