Algorithm/DP(Dynamic Programing) (72) 썸네일형 리스트형 (C++) - 백준(BOJ) 11660번 : 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 2차원 부분합이었습니다. 풀이방법 2차원 넓이 면적으로부터 다른 2차원의 넓이를 적절히 뺴는 방법을 생각합니다. Code #include #define fastio ios::sync_with_stdio(false); cin.tie(NULL); using namespace std; long long a[1025][1025],s[1025][1025]; int.. (C++) - 백준(BOJ)코딩 1149번 : RGB거리 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2차원 bottom up dp로 풀었습니다. 풀이방법 D[i][j] = i번째 집을 j색으로 칠할 때 최소 비용 빨강:1 초록:2 파랑:3 D[1][1] = A[1][1]; D[1][2] = A[1][2]; D[1][3] = A[1][3]; A[i][j] = 입력 j로 칠했을 때 i-1, i+1번째 집은 j색으로 칠할 수 없다. 1.i번째 집을 R로 칠했을 때 (2 (C++) - 백준(BOJ) 11051번 : 이항 계수2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net dp로 푼 문제였습니다. 풀이방법 D[i][j] = nCk; D[i][j] = D[i-1][j-1] + D[i-1][j] Code 1. bottom up #include using namespace std; long long D[1001][1001],N,K; int main() { cin >> N >> K; D[1][0] = D[1][1] = 1; for (int i = 2; i n >> k; cout (C++) - 백준(BOJ)코딩 2579번 : 계단오르기 답 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 2차원 bottom up dp로 풀었습니다 풀이방법 1. 각 계단을 stair[i]로 입력 받습니다. 2. 점화식을 생각합니다. i번째 계단을 올라갔을 때 몇 번 연속해 올라가 있는지에 대한 상태가 필요하므로 2차원 배열 d를 선언합니다. d[i][j] = i번째 계단을 j번 연속으로 올라갈 때 최대값 d[i][1] => 1번 연속으로 올라갔으므로 i-2번째 계단은 올라가거나 건너뛰거나 상관없습니다. 따라서 다음 점화식을 .. (C++, Python3) - 백준(BOJ) 11055번 :가장 큰 증가 부분 수열 답 https://www.acmicpc.net/problem/11055dp문제였습니다.📕 풀이방법📔 입력 및 초기화배열길이 n과 배열을 arr를 선언 후 입력받습니다.📔 풀이과정완전 탐색으로 i까지 도달했을 때 가장 큰 증가 부분 수열의 값을 d[i]라 하면 다음과 같은 점화식이 가능합니다. $${ if \ arr[i] > arr[j] \ D[i] = MAX(D[j](0arr[i]가 가장 큰 값이므로 그보다 작은 arr[j]를 발견할 경우 그때의 D[j]값에서 현재 선택 값인 arr[i]를 더한 값의 최댓값을 d[i]에 저장하면 됩니다. n이 1000까지이므로 O(N^2)로 동작 가능한 풀이입니다.📔 정답 출력 | 반환정답 배열의 가장 큰 원소를 반환합니다.📕 Code📔 C++#include .. (C++) - 백준(BOJ) 13699번 : 점화식 https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 i항의 값을 저장할 일차원 t배열, int 형 변수 n을 선언 후 n을 입력받습니다. 📔 풀이과정 top down dp를 통해 답을 반환해줍니다. 재귀함수의 동작방식은 이렇습니다. 1. 기저 케이스는.. (C++) - 백준(BOJ) 9657번 : 돌 게임 3 답 www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 간단한 dp문제였습니다. 풀이방법 돌을 1개 선택, 3개 선택, 4개 선택하는 경우 이 중 하나라도 질 수 있다면 상근 승, 아니라면 창영 승 Code #include using namespace std; int main() { int num, arr[1001] = { 0,1,0,1,1 }; cin >> num; for (int i = 5; i (C++) - 백준(BOJ) 2748번 : 피보나치 수 2 https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 대표적인 dp문제였습니다. Code 1. Top down dp #include #define ll long long using namespace std; ll fibo[91], n; ll dp(int num){ if(num == 1 || num == 2) return 1; ll &ret = fibo[num]; if(ret) return ret; ret = 0; .. 이전 1 ··· 6 7 8 9 다음