본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm/Dynamic28

[동적계획법, 난이도 중] 백준 11052번 카드 구매하기 카드팩을 고를 때 중복을 허용한다는 점에서 조금 까다로울 수 있다. 그러나 이 문제도 점화식 한줄로 풀 수 있다. 카드를 가질 수 있는 경우는 무수히 많기 때문에 동적계획법으로 제한 장 수별로 최댓값을 구해놓아야 한다. 카드를 n개 가져야 할 경우 카드n개팩 그 자체가 가장 비쌀 수도 있고, 카드 n-i개 팩을 사는 최대비용의 경우에 i개 팩을 추가로 샀을 때가 가장 비쌀 수도 있다. 이렇게 동적 계획법으로 접근하면 n개의 경우만을 계산하여 최댓값을 구할 수 있다. 본인이 가져온 예제는 입력 예제4 이다. 처음 한 개 팩을 사는 비용은 5이다. 카드 2장을 사는 경우의 수는 (카드 2장짜리 팩값, 카드 1장을 사는 최대 비용 + 카드 1장짜리 팩값) 이 둘이고, 모두 비용은 10이라 표시는 안난다. 카드.. 2020. 8. 28.
[동적 계획법, 난이도 중] 백준 9465번 스티커 입력이 단순히 일렬로 주어지지 않고, 2차원 표 형식으로 주어지는 종류의 DP문제다. 스티커를 인접하지 않게 고를 수 있는 최대 점수를 계산하는 문제다. 그래도 이 문제는 O(N) 의 시간 복잡도로 해결 할 수 있다. 스티커가 2행 n열로 배치되어 있는데 1열당 2개의 스티커씩 n회 만큼만 DP를 수행하면 된다. 이런 유형의 DP는 한 열 단위로 DP를 수행하려고 하지말고 각 열의 1행, 2행에 대한 DP를 모두 수행해야 한다. 이 문제에서 주어진 예제로 DP를 수행하는 원리를 설명한다. 진행은 1열부터 n열 순으로한다. 입력값 50 10 100 20 40 30 50 70 10 60 두 인접한 스티커는 같이 고를 수 없으므로 초기값은 1열의 값 그대로다. 이제 2열은 위에서 부터 스티커 점수가 10, 5.. 2020. 8. 27.
[동적계획법, 난이도 중] 백준 14501번 퇴사 회사에서 매일 회의가 열리고 각 회의의 기간과 받는 금액이 주어졌을 때, 최대 수익을 계산하는 문제이다. 각 Day마다 열리는 회의가 끝난 후 새로 시작할 수 있는 날을 기록해두고, 현재 Day를 기준으로 이미 끝나 있는 회의 중에서 누적 최대 수익이 큰 경우를 고른 뒤에, 현재 날짜의 회의를 진행하는 식으로 접근하면 된다. 아래 표를 보면 이해가 더 잘될 것이다. S0은 각 Day마다 현재 날짜에 회의 기간을 더한 값들이고, 회의가 끝난 날+1 = 새로 시작할 수 있는 날을 의미한다. 1일차의 경우에는 3일에 걸쳐 회의가 진행되므로 4일차에 새로운 회의를 시작할 수 있다. 즉, S0[1]=4 가 된다. 이런식으로 S0는 쉽게 계산 할 수 있고, S1에 해당하는 DP는 2일차 때부터 진행하면 된다. 현재.. 2020. 8. 26.
[동적계획법, 난이도 중] 백준 9461번 파도반 수열 DP는 점화식은 짧지만 생각이 결론에 도달하여 점화식을 만드는데까지는 시간이 다소 오래 걸린다는 특징이 있다. 특히 이런 도형문제가 그런 편인 것 같은데, 도형쪽으로 센스가 있다면 쉽게 풀 수 있을 것이다. 기준이 되는 첫 삼각형은 크기가 1인 정삼각형이라고 했는데, 아래에 빨간 테두리로 쳐 둔 정삼각형이 기준인 것 같다. 그래야 시계 방향으로 자연스럽고 보기좋게 갱신이 가능하다. 여기서 잘 보면 4번째 삼각형을 처음 포함했을 때부터 쭉 오각형 형태가 유지되며, 6번째 삼각형을 포함하게 될 때부터 새롭게 포함되는 삼각형은 2개의 삼각형 변과 인접하게 된다. 그 2개의 삼각형은 i를 현재 포함하려는 삼각형이라고 하면, i-5번째 삼각형과 i-1번째 삼각형에 해당된다. 이해를 돕기 위해 아래 그림을 첨부하였.. 2020. 8. 25.
[동적계획법, 난이도 중] 백준 11053번 가장 긴 증가하는 부분 수열 제한 시간은 1초며, N의 범위가 (1 ≤ N ≤ 1,000) 으로 좁은 편이기 때문에 O(N^2) 까지 쓸 수 있다. 그래도 이 문제는 1차원 배열의 DP로 풀 수 있다. 첫 INPUT에 대한 DP의 첫 인덱스 값을 1로 두며 시작한다. 그리고 이 조건에 따라 뒤 INPUT값들에 대해 DP를 수행해주면 된다. 현재 INPUT값보다 작은 모든 이전 INPUT값들의 각 DP값들중 최댓값에 1을 더한 값을 현재 DP값으로 지정한다. 만약 현재 INPUT값이 30이라면 이전 INPUT값들은 각각 10, 20, 10이고, 이들의 각 DP값은 1,2,1이다. 1,2,1의 최댓값은 2이기 때문에 이에 1을 더한 3을 현재 DP값으로 지정하는 것이다. 현재 INPUT값이 지금까지 나온 INPUT값들중 최솟값일 경우가.. 2020. 8. 24.
[동적계획법, 난이도 중] 백준 10844번 쉬운 계단 수 이 문제에서 신경써야 할 조건들이다. - 인접한 모든 자리수의 차이는 1이어야 한다. - 0으로 시작할 수 없다. - 정답을 10억으로 나눈 나머지를 출력해야 한다. 아마 이 문제의 정답율이 낮은 이유는 long long 자료형을 모르는 분들이 많아서 그런 것같다. int는 약 21억을 넘어가면 이상한 값이 나오는데 쓰레기 값이라고 하기도 한다. 이 때 int 대신 범위가 훨씬 더 넓은 long long을 써주면 된다. 계산할 때마다 10억으로 나눈다곤 하지만 이런 10개의 변수들을 모조리 합 한다면 21억을 넘을 경우는 충분히 생긴다. 아래 표에서 행은 맨오른쪽 끝의 자리수를 의미하며, 열은 숫자의 길이를 의미한다. 즉 DP[i][j] 값은 길이가 j이며 맨마지막에 i라는 자리수가 오는 경우의 수이다... 2020. 8. 20.
[동적계획법, 난이도 중상] 백준 1912번 연속합 연속된 자릿값을 더해서 나올 수 있는 최댓값을 구하는 문제이다. 이 문제는 아주 특수한 경우 하나를 처리해줘야 한다. - 양수가 하나도 입력 되지 않았을 경우 이 경우에는 입력 값들의 최댓값이 정답이 된다. 이제, 나머지의 경우에 대해 DP를 수행해보자. 위 사진은 내 접근법에 대한 DP표이다. 먼저, 첫 번째 dp인덱스의 값은 첫 번째 입력값과 동일하다. 그리고 이후의 dp인덱스에 대해서는 다음과 같은 식을 이용했다. d[i]=max(0, d[i-1]+e[i]); #include #include using namespace std; int e[100001]; int d[100001]; int n, ans; int maxi=-1000; int main() { cin>>n; for(int i=1;i>e[i.. 2020. 8. 19.
[동적계획법, 난이도 중] 백준 2156번 포도주 시식 백준 2579번 계단 오르기와 접근법이 비슷하다. https://kimcoder.tistory.com/54 [동적계획법, 난이도 중하] 백준 2579번 계단 오르기 이 문제의 주어진 조건을 요약하자면, 계단을 3칸 연속으로 밟을 수 없고 마지막 칸은 무조건 밟아야 한다는 것이다. 배열 save를 n번째 계단까지 올랐을 때 얻을 수 있는 최대 점수, 배열 floors을 � kimcoder.tistory.com 이 문제에서 주어진 조건은 1가지이다. - 연속되는 3자리의 포도주를 시식할 수 없다. 백준 2579번 계단 오르기 문제 조건과 차이점은 단 한 가지다. 마지막 자리를 꼭 선택할 필요가 없다는 것이다. 아래 사진에서 연한 노랑색은 이미 계산된 DP결과이고, 진한 노랑색은 시식할 수 있는 포도주 자리들.. 2020. 8. 19.
[동적계획법, 난이도 중하] 백준 2193번 이친수 문제에 주어진 조건은 2가지이다. 1. 첫 번째 자리는 0이 될 수 없다. 2. 1이 두 번 연속으로 나타날 수 없다. 이 말은 n-1번째 자리가 0이라면 n번째 자리에는 0과1이 모두 올 수 있고 n-1번째 자리가 1이라면 n번째 자리에는 0만 올 수 있다는 것이다. 0은 첫 번째 자리 외엔 어느 자리에나 올 수 있으므로 n번째 자리가 0인 경우의 수는 n-1번째 자리가 0인 경우의 수와 n-1번재 자리가 1인 경우의 수의 합 1은 n-1번째 자리가 0인 경우에만 올 수 있으므로 n번째 자리가 1인 경우의 수는 n-1번째 자리가 0인 경우의 수 각 자리수의 두 경우의 수를 합한 결과가 이 문제의 답이다. 이를 표로 정리하면 이렇다. (예시로 n=7까지 작성) 예제 입력1) n=3인 경우 답은 2+1=3.. 2020. 8. 19.

티스토리툴바