본문 바로가기

Algorithm/DP(Dynamic Programing)

 (64)
(C++) - 백준(BOJ) 10025번 : 게으른백곰 답 https://www.acmicpc.net/problem/10025 10025번: 게으른 백곰 문제 더운 여름날 동물원의 백곰 앨버트는 너무 더워서 꼼짝도 하기 싫다. 다행히도 사육사들이 앨버트의 더위를 식히기 위해 얼음이 담긴 양동이들을 가져다 주었다. 앨버트가 가장 적은 거리만 움직이고도 최대한 많은 얼음으로 더위를 식힐 수 있도록 도와주자. 우리 안은 1차원 배열로 생각하며, 총 N(1> x; ice[x] = g; } d[0] = ice[0]; for (int i = 1; i
(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++) - 백준(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; ..

티스토리툴바