다이나믹 프로그래밍

(Python) 백준 1912번 - 연속합

문제 링크: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 Dynamic Programming 문제답게 코드 구현보다는 문제 해결을 위한 아이디어를 생각하는 것이 더 어려운 문제이다. 문제 해결을 위한 아이디어는 다음과 같다. 우선 해당 인덱스까지의 최대값을 담을 배열을 선언한다. 그 후 처음부터 순회하며 해당 인덱스까지의 최대값을 계산하고 이를 저장한다. 해당 인덱스까지의 최대값은 이전 인덱스에서의 최대값 또는 현재 인덱스의 값이 된다. 최종적으..

(C++) 백준 11051번 - 이항 계수 2

문제 링크 : https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 풀이 이항 계수의 성질 중 다음의 파스칼의 삼각형을 사용하여 풀었다. 처음에 재귀함수를 사용하여 풀이하였으나 그럼 시간 초과가 발생하기에 다음과 같이 dp로 풀이하였다. #include using namespace std; int n, k; int bicos[1005][1005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; bicos[0][0] = bi..

(C++) 백준 12852번 - 1로 만들기 2

문제 링크 : https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 활용하여 풀이하였다. 백준 1463번과 마찬가지로 입력이 1일 때 0, 입력 2일 때 1이라는 초기값을 부여해 주고 그 이후에 상황에 맞춰 1씩 더해주는 방식으로 풀이하였다. 그리고 연산의 순서대로 출력을 해야 하므로 1로 가는 경로에 있는 다음 값을 배열에 저장하였다. ex) arr[16] = 8, arr[8] = 4, arr[4] = 3, arr[3] = 1 #include using namespace std; int arr[1000005]; int hist..

(C++) 백준 11659번 - 구간 합 구하기 4

문제 링크 : https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 다이나믹 프로그래밍을 사용하여 풀이하였다. 처음부터 특정 인덱스까지의 합을 배열에 저장하고, 구간 사이의 합을 구하기 위해 특정 인덱스까지의 합(sum[j-1])에서 구간에 속하지 않는 값의 합(sum[i-2])을 빼는 방식으로 구현하였다. #include using namespace std; int sum[100002]; int num[100002]; ..

(C++) 백준 11726번 - 2xn 타일링

문제 링크 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 사용하여 풀이하였다. 2*N 크기의 타일을 채우는 방법은 제일 처음 1*2 크기의 타일을 먼저 채웠을 경우와 제일 처음 2*1 크기의 타일 2개를 먼저 채우고 시작할 경우의 합이다. 즉 2*(N-1) 크기의 타일을 채우는 방법과 2*(N-2) 크기의 타일을 채우는 방법의 합을 구하면 된다. #include using namespace std; int tile[1002]; int..

(C++) 백준 1149번 - RGB 거리

문제 링크 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2차원 배열을 사용해서 house[x][0]은 x번째 집이 빨간색일 때의 최소 비용, house[x][1]은 x번째 집이 초록색일 때의 최소 비용, house[x][2]은 x번째 집이 파란색일 때의 최소 비용을 저장하도록 하였다. #include #include using namespace std; int hous..

(C++) 백준 2579번 - 계단 오르기

문제 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2차원 배열을 사용해서 arr[x][0]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟지 않았을 경우, 즉 x-2번째 계단을 밟았을 때로, arr[x][1]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟았을 경우, 즉 x-1번째 계단을 밟았을 때이다. 마지막으로 다이나믹 프로그래밍을 진행할 때 x-2가 인덱스일 때의 값이 필요하므로 초기값으로 ..

(Python) 백준 2839번 - 설탕 배달

문제 링크 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 처음엔 그리디 알고리즘으로 접근하려다가, 문제에서 제시된 봉지의 용량이 3kg , 5kg으로 배수의 관계가 아니기 때문에 불가능함을 깨닫고 다이나믹 프로그래밍으로 풀이를 진행했다. import sys n = int(sys.stdin.readline()) arr = [5001] * (n+1) # 문제에서 주어지는 최대 무게가 5000kg이므로 만들 수 없는 경우를 5001로 설정 arr[0..