본문 바로가기

Algorithm/DP(Dynamic Programing)

 (64)
(C++) - 백준(BOJ) 9625번 : BABBA 답 www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net dp문제였습니다. 풀이방법 1. i번째의 a는 i-1번째의 b로 대체됩니다. 2. i번째의 b는 i-1번쨰의 a와 i-1번째의 b로 대체됩니다. Code #include using namespace std; int a[45]; int b[45]; int pushed; int main(void){ cin >> pushed; a[0]=1; b[1]=1; for (int i = 2; i < pushed + 1; i++)..
(C++) - 백준(BOJ) 2346번 : 풍선 터뜨리기 답 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 간단한 dp문제였습니다. 풀이방법 1. 00타일 : 길이 2 1타일 : 길이 1 인 정보를 가지고 있습니다. 길이[i-1]인 타일을 만들 수 있는 경우의 수 = 다음에 1타일을 연결하면 길이 i가 됩니다. => 1타일사용 길이[i-2]인 타일을 만들 수 있는 경우의 수 = 다음에 00타일을 연결하면 길이 i가 됩니다. => 00타일사용 따라서 길이 i인 타일을 만들 수 있는 경우의 수 = 길이[i-1]인 타일을 만들..
(C++) - 백준(BOJ) 13703번 : 물벼룩의 생존확률 답 www.acmicpc.net/problem/13703 13703번: 물벼룩의 생존확률 수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를 www.acmicpc.net dp문제였습니다. 풀이방법 생존할 경우 : 제한시간 n초 안에 수면에 가지 않을 때 생존 경우 수 추가 생존 경우 수 : 위로튈때 생존경우 수 + 아래로 내려갈때 생존경우 수 Code #include #include #define ll long long using namespace std; ll height,second; ll flee[1000][1000]; ll dp(ll k,ll n){ ll &ret..
(C++) - 백준(BOJ) 14720번 : 우유축제 답 www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후�� www.acmicpc.net dp문제였습니다 풀이방법 d[n][k] : 위치 n에서 k종류의 우유를 마셨을 때 최대 마신 우유 개수 답 : max(만약 현재위치 n에서 k종류를 마실 차례가 되었다면 그 우유를 마셨을 때 개수, 현재 위치 우유를 마시지 않았을때의 우유 개수) Code #include using namespace std; int num, n; int d[1000][3]; int milk[1000]; int dp(int n,i..
(C++) - 백준(BOJ) 10653번 : 마라톤 2 답 www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net dp로 푼 문제였습니다. 풀이방법 d[n][k] : n번째 체크포인트를 선택했을 때 k개만큼 건너뛰었을 때의 최소 거리일 때 점화식은 다음과 같습니다. 0 k; for(int i = 1; i > v[i].first >> v[i].second; } memset(d,-1,sizeof(d)); for(int i = 1; i
(C++) - 백준(BOJ) 17626번 : Four Squares 답 www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net dp문제였습니다. 풀이방법 i라는 제곱수를 구하기 위해 필요한 최소 숫자의 개수는 min(dp[i], j = 1부터 루트 i까지 dp[j*j] + dp[i-j*j]) 입니다. Code #include #include #include using namespace std; int n; vector dp (50001,0x7f7f7f7f); int main(){ cin >> n; f..
(C++) - 백준(BOJ) 13302번 : 리조트 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 즐기기 위해서는 하루로는 터무니없이 부족하다. 그래서 많은 이용객들은 3일 이상 연속으로 이용하기도 한다. KOI 리조트에서는 3일 연속 이용권을 할인된 가격 이만오천원에, 연속 5일권은 삼만칠천원에 판매하고 있다. 게다가 연속 3일권, 연속 5일권에는 쿠폰이 각각 1장, www.acmicpc.net Top-Down dp문제였습니다. 12345678910111213141516171819202122232425262728293031323..
(C++) - 백준(BOJ) 10835번 : 카드게임 https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1 ≤ B ≤ 2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다. www.acmicpc.net Top-down dp 기본문제였습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #incl..

티스토리툴바