BOJ (22) 썸네일형 리스트형 [BOJ][DP] 1937. 욕심쟁이 판다 문제 -> https://www.acmicpc.net/problem/1937 처음에는 메모이제이션 생각을 안하다가 혹시 탐색으로 풀어야 하나 해서 해봤더니 바로 성공.. 너무 틀에 박힌 생각만을 해온것이 아닌가 걱정이다. 재귀도 꼭 고려해보자 이 놈아 ㅠㅠ ============================================ 메모이제이션, 즉 메모화 재귀도 DP에 포함되는 분야다. 메모이제이션이 무엇이냐 하면은,.. 간단히 말해서 재귀 호출로 인한 어떤 값을 저장하여 똑같은 값을 얻으려 재귀가 시도될 때 연산을 하지않고, 그 기억된 값을 사용하는 것 . 즉, 중복을 없앤다. ============================================ 어떻게 푸냐 하면은 1. 그 곳에 있는 .. [BOJ][DP] 2225. 합분해 문제 -> https://www.acmicpc.net/problem/2225 자릿수가 증가함에 따라 어떻게 경우의 수를 구해야 할지 단순하게 생각해야 한다. 뭐든지, 문제는 단순화 시킨 후 확장. 예를들어 N = 7, K = 3인 상황을 생각해보자. 단순하게 K자리에 N 부터 0 까지 차례대로 들어가고, N - K자리에 있는 값을 합으로 가지는 K-1 자리의 dp값을 가져오면 된다. 즉, 점화식은 아래와 같다. dp[i][j] += dp[i - 1][j - k]; (3중 for문으로 쓰여서 i, j, k가 쓰였다.) 그림을 보면 이해가 될지도 모른다. 아래는 위 과정을 표로 나타냈다. 소스(Github) [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] 1904. 01타일 문제 -> https://www.acmicpc.net/problem/1904 N이 홀수일 때, N이 짝수일 때 어떤 경우가 나올지 잘 생각해보면 금방 답이 도출이 된다.. 아래 그림을 보자. 먼저 N=0일 때, 타일을 배치하지 않는다 라는 선택도 경우의 하나에 속하므로 1. N = 1일 때, 1밖에 놓을 수 없으므로 경우는 1. N = 2일 때, 00, 11 두 개밖에 놓을 수 없으므로 2. 이제부터가 중요하다 . N = 3일 때, 100, 001, 111로 총 세가지이다. N이 홀 수라면,낱개로서 배치할 수 있는 타일인 "1"한개가 들어가는 경우가 생긴다. 그래서 경우의 수에 영향을 주게된다. 여기서 가만보면 어떤 점화식을 도출해낼 수가 있다. dp[i] = dp[i - 2] * 2 + dp[i-3] .. [BOJ][DP] 11054. 가장 긴 바이토닉 수열 문제 -> https://www.acmicpc.net/problem/11054 이 문제 역시 바로 감이 온다. 가장 긴 증가하는 부분 수열 오른쪽, 오른쪽 -> 왼쪽 이렇게 두번의 연산을 각각 한 후 두 연산한 값을 모두 더해 제일 큰 것이 답이 되겠다. 여기서 주의해야 할 점은 왼->오. 오->왼 둘다 자기 자신을 포함한 상태이기에 결과를 출력할 때 무조건 -1을 해줘야한다. 소스(Github) [BOJ][DP] 9251. LCS 문제 -> https://www.acmicpc.net/problem/9251 이 문제도 아주 곤욕을 치뤘다. http://twinw.tistory.com/126 dp[i][j] = dp[i-1][j-1] + 1; 2) 알파벳이 다른 경우-> dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 왜 위와 같이 나오는지는 위의 링크를 가서 설명을 보면 명쾌히 풀릴 것이다. 감사드립니다 White Whale님.. 소스(Github) [BOJ][DP] 11722. 가장 긴 감소하는 부분 수열 문제 -> https://www.acmicpc.net/problem/11722 이 문제 또한 가장 긴 증가하는 부분 수열의 풀이와 동일하다. 가장 긴 증가하는 부분 수열 -> http://tiredsleeper.tistory.com/33?category=782681 차이점이 있다면, 증가하는 부분 수열 문제에서는숫자[i] 보다 작은 수에 대해 dp값을 비교하는 것이었지만, 이번에는 거꾸로다.숫자[i]보다 큰 수에 대해서 dp값을 비교해야한다.감소한다는 것은 큰 값에서 작은값이 된다는 것이니. 소스(Github) 이전 1 2 3 다음
