본문 바로가기

다이나믹 프로그래밍

BaekJoon 2752 보드게임 2019. 1. 31. Link https://www.acmicpc.net/problem/2572 소스 결과 3148 KB / 0 ms 출처 Baekjoon , KOI 2007 고등부 3번 언어 C++ 17 분류 다이나믹 프로그래밍 설명 R G B 3가지 색깔이 있는 보드게임 카드를 가지고 문제의 룰을 통해 얻을 수 있는 최대 점수를 구하는 문제 처음에 접근을 카드를 기준으로 접근을 한게 아닌, 정점을 기준으로 접근을 했더니 아니나 다를까 메모리가 터졌다. 문제의 접근을 현재 위치와 이번에 내는 카드를 기준으로 접근을 해야했다. 현재 카드를 기준으로 접근 할 수 있는 정점의 값을 기록해 모든 카드를 소모 할 때 까지 반복한다. 알고리즘 1. 정점의 정보를 받아 저장한다. 2. 1번 정점을 시작으로 방문 할 수 있는 정점의 점수..
BaekJoon 1912 연속합 2019. 1. 14. Link https://www.acmicpc.net/problem/1912 소스결과 2652 KB / 8 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹 프로그래밍, 수학 설명 임의의 수열에 대해서 연속된 수의 합이 최대를 구하는 문제 예제만 보고 양수의 합을 구하다가 다음 수가 음수가 나오면 현재 까지의 합을 남기는 알고리즘을 만들었다가 오답 한개를 추가하고 시작했다. 위 예제에서 -35를 21 뒤에 놓는 형태로 바꾸면 문제에 숨겨진 함정이 나온다. 음수가 존재 한다고 해서 그 다음 수를 더했을 때 현재 까지의 합이 최대라는 보장이 없는 함정이 숨어 있다. DP Table 조금 변형을 가해서 현재까지의 합 + 다음 수의 합이 음수가 된다면 음수의 그 다음수가 양수여도 현재 합을 넘을 수 없는..
BaekJoon 11726 2xn 타일링 2019. 1. 14. Link https://www.acmicpc.net/problem/11726 소스결과 1984 KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹 프로그래밍 설명 2 x n 에 1 x 2, 2 x 1 타일로 채우는 방법의 수를 구하는 문제 DP의 기초를 다지기에 좋은 문제 먼저 결론부터 말하면 위 문제는 피보나치 수열의 형태를 띈다 2 x 5까지 경우의 수를 계산해 보면 피보나치 수열의 형태를 가진다 주의할 점은 경우의 수를 10007로 나눈 나머지를 구해야 한다. 피보니치 수열을 계산 한 후에 꼭 % 10007 연산을 통해 나머지를 저장하도록 하자 소스코드 #include using namespace std; const int MAX = 1000; int main() { int dp..
BaekJoon 2193 이친수 2019. 1. 14. Link https://www.acmicpc.net/problem/2193 소스결과 1984 KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹 프로그래밍 설명 0으로 시작하지 않으면서 1이 연속으로 두번 나오지 않는 N 자리의 이진수의 개수를 구하는 문제 각각의 경우를 계산 해보면 1 : 1 ( 1개 ) 2 : 10 ( 1개 ) 3 : 100 101 ( 2개 ) 4 : 1000 1001 1010 ( 3개 ) 5 : 10000 10001 10010 10100 1010 1 ( 5개 ) 피보나치 수열이다 아래의 점화식을 이용하자 dpTable[i] = dpTable[i - 1] + dpTable[i - 2]; ( 단 i > 1 ) 소스코드 #include using namespace st..
BaekJoon 1149 RGB 거리 2019. 1. 14. Link https://www.acmicpc.net/problem/1149 소스결과 2012 KB / 0 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹프로그래밍 설명 이웃한 집과 같은색으로 칠하지 않으면서 모든 집을 칠할 때 드는 비용의 최솟값을 출력하는 문제 이전 집의 색을 기억해서 같은 색이면 그 색을 제외하고 최솟값을 구해 마지막까지 칠하는 경우 모든 경우에서 최솟값을 선택하는 그리디 알고리즘을 적용시키면 문제의 정답이 나오지는 않는다. 같은 값이 존재하는 경우 위치에 따라 다른 결과 값이 나올 수 있다는 점을 유의해야한다. 또한 매번 최선의 선택이 정답이 되지 않기 때문에 모든 경우에 대해서 검사를 해야 한다. DFS로 풀어나가면 시간 초과가 나온다. 점화식은 첫 번쨰 경우를 제외하고..
BaekJoon 1003 피보나치 함수 2019. 1. 14. Link https://www.acmicpc.net/problem/1003 소스결과 1984 KB / 8 ms 출처 Backjoon 언어 C++ 17 분류 다이나믹 프로그래밍 설명 문제에 나와 있는 소스 코드를 기반으로 0이 출력되는 경우와 1이 출력 되는 경우의 수를 출력하는 문제 저 함수를 직접 코드화 시켜서 printf 문 대신 0 인덱스를 1씩 추가시키면 시간 초과의 늪으로 들어간다 테스트 케이스 범위도 좁은 만큼 시간 제한도 0.25초로 매우 빡세다 점화식을 세우기 위해 0부터 4까지 계산해보면 0 : 1 0 1 : 0 1 2 : 1 1 3 : 1 2 4 : 2 3 이라는 결과를 바탕으로 0 이 출력되는 경우의 수와 1이 출력되는 경우의 수에 대해서 피보나치 수열처럼 구현하면 된다. 따라서 점화..

티스토리툴바