huiyu's blog

백준 기업투자 문제 : https://www.acmicpc.net/problem/2662 문제 요약- 일정금액을 기업들에게 돈을 투자해서 최대 이익을 얻고자한다.- 투자액이 정해져 있고 기업의 개수와 기업에 투자할 이익이 주어질 때, 가장 많은 이익을 얻을 수 있는 투자방식과 이익금을 구하기위의 경우 최대 이익을 얻는 경우는 B기업에만 4만원을 투자하는 경우 15만원입니다. 우선 문제의 기본 입력을 받고 필요한 함수를 구현합니다.123456789101112131415161718192021222324252627282930#include using namespace std; int arr[301][21];int DT[301][21]; int M, C; int MAX(int a, int b){ return (..

백준 9465번 스티커 문제 풀이 : https://www.acmicpc.net/problem/9465 문제요약 : - 2xn개의 스티커를 갖고있다. 각 스티커는 점수가 있다.- 스티커를 떼면 그 스티커와 변을 공유하는 스티커는 찢어져 사용할 수 없다(점수x)- 뗄 수 있는 스티커 점수의 최댓값을 구하시오. 우선 이런 유형의 문제는 완전탐색을 하여 구현을 해봅니다.. 그다음 DP를 적용.. 1. 완전탐색을 할 경우를 생각해봅니다. "-->" 오른쪽 방향으로 탐색을 했을 때, 스티커를 떼는 방법은 위를 떼는 방법, 그리고 아래를 떼는 방법 두가지가 존재합니다. 우선 공유하는 변의 스티커가 뜯어지는 경우를 무시하고 전체 경우를 구한다면, 아래와 같이 구현할 수 있습니다. 12345678int solve(in..

1. 동적 계획법(Dynamic Programming)이란?분할 정복과 같은 접근방식을 갖고 있습니다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문입니다. 차이가 발생하는 부분은 문제를 나누는 방식입니다. 부분문제가 여러번 사용될 수 있을 때 여러번 중복 계산하는 것이 아닌, 한번만 계산하고 저장해둬 재활용해 사용합니다. (a)서로 연관이 없는 부분문제 (b)서로 의존하고 있는 부분문제 (a)는 서로 연관이 없어 단순히 재귀 호출을 통해 문제를 풀어도 한 부분문제를 한 번만 해결합니다. (b)는 부분문제가 서로 의존하고 있어, 단순 재귀로 풀면 중복 계산이 많아집니다. 예를 들면 cde는 abcde를 해결할 때, cdef..