Algorithm (6) 썸네일형 리스트형 [BOJ][DP] 1965. 상자넣기 문제 -> https://www.acmicpc.net/problem/1965 LCS인가 여튼 이와 비슷하게 접근하여 문제를 해결할 수 있다. 문제를 잘 읽어보아야 하는게, 입력된 상자의 데이터가 있을 때, 그 데이터의 위치를 가지고 판단을 해야한다. (처음에 그냥 막무가내로 풀었다가 실패) 또한, 저 상자들을 최대한 넣어서 어떤 무지막지하게 큰 상자에 넣는것이다. 즉, 조건을 만족하는 상자의 개수를 세는 것. 그러면 상자는 어떻게 세느냐? arr[i]보다 작은 값 arr[x] (x < i) 에 대해 dp값을 조사한다. 제일 큰 dp값을 기억해서 + 1. 1, 5, 2, 3, 7 의 예시로 해보자. 처음에는 모든 값이 0. 1의 왼쪽에는 작은 더 작은 수가 없으므로 그냥 +1. 이어서 "5"는 왼쪽에 더 .. [BOJ][DP] 1309. 동물원 문제 -> https://www.acmicpc.net/problem/1309 코드 자체는 짧지만 아이디어가 중요한 문제. 단순하게 문제를 생각해야 비로소 답이 보인다. 한 사자가 놓여져있을 때, 그 놓인 사자의 가로, 세로의 방향으로는 사자를 놓을 수가 없으므로 아래와 같이 대각선으로 놓든, 아무 사자도 놓지 않는 경우가 있다. N번째줄 칸에 칸이 놓일 수 있는 경우는 N-1번째줄 칸의 사자 배치의 상태에 따라 달라진다. 위 그림을 보면 알아 챌 수도 있지만, N-1번째줄에 어떤 한 칸이 있으면 그 밑에 사자를 배치할 수 있는 경우의 수는 각각 2개씩. N-1번째줄에 아무 사자가 없으면 그 밑에 배치할 수 있는 경우는 3개. 즉, 경우를 두 개로 나누어서 생각해야 한다는 것. 그렇다면 점화식은 dp[i].. [BOJ][DP] 11055. 가장 큰 증가 부분 수열 문제 -> https://www.acmicpc.net/problem/11055 가장 긴 증가 부분 수열 문제와 동일하게 접근하면 된다. 다만, 달라진 점은 길이가 아니라 합이라는 점. 아마 거의 소스가 동일할 것이다. 소스(Github) [BOJ][DP] 1699. 제곱수의 합 https://www.acmicpc.net/problem/1699 처음에는 문제에 대한 접근을 일단 될 수 있는대로 큰 제곱수 (x [BOJ][DP] 2156 포도주 시식 https://www.acmicpc.net/problem/2156 개인적으로 생각하는데 꽤 시간이 든 문제.. 지금 돌아보니 그렇게 오래 걸릴 문제는 아닌 것 같은데.. 뭐, 다 그런게지. 이 문제에서의 포인트. 연속으로 놓여있는 3개 이상의 포도주를 마실 수 없다. DP는 항상 어려운게, 점화식 하나 세우는게 힘들다. 작은 경우에서 큰 경우로 확장을 시키면서 점화식을 만들어야 하는게 DP의 포인트. ~식으로 ~처리가 되어서 결국 마지막에 x 값이 제일 큰 값이 된다. 라는 전개를 해야한다. 포도주의 용량을 담는 배열을 wine. 각각의 dp값을 담는 dp배열이 있을 때, N개의 와인이 있으면, 시식하는 3가지의 경우가 발생한다. 1. N번째 와인을 마시고 N-1, N-3 와인을 .. [BOJ][DP] 1932. 숫자삼각형 https://www.acmicpc.net/problem/1932 DP 문제다. 문제에서 우리가 잡아내야 할 포인트는 1. 이제까지 선택된 수의 합이 최대가 되는 경로.2. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼/오 중 하나를 선택. 점화식을 세우기 위해서 일단 이해를 해보자. 문제에서는 수들을 삼각형의 형태로 나타내었지만, 어렵게 생각할 필요가 없다.위에서부터 차례대로 배열에 넣어주면 아래와 같다. 그럼 여기서 어떻게 어떠한 값에 대한 왼/오 대각선 값을 가리킬 수 있을까? 보다시피 한 값의 인덱스 +2 = L, +3 = R 이 되는것을 알 수있다. 얼추 이해가 오기 시작하는가?그렇다면 이제 여태까지 이해한 것을 바탕으로 점화식을 세워보자.(arr은 입력받았던 값을 저장해둔 배열이다.).. 이전 1 다음
