선호:하다

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/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net import sys from bisect import bisect_left n = int(sys.stdin.readline()) data = list(map(int, sys.stdin.readline().rstrip().split())) dp = [data[0]] for i in range(1, n): if data[i] > dp[-1]: dp.append(data[i]) else: idx = b..

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} 이때 개미 전사는 두 번째 식량창고와 네 ..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net import sys n, c = map(int, sys.stdin.readline().rstrip().split()) data = [] for i in range(n): data.append(int(sys.stdin.readline())) data.sort() start = 1 end = data[-1] - data[0] while start =..

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

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net import sys k, n = map(int, sys.stdin.readline().rstrip().split()) data = [] for i in range(k): data.append(int(sys.stdin.readline().rstrip())) start = 1 end = max(data) while start = n: start = mid + 1 else:..