Baekjoon (16) 썸네일형 리스트형 [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] 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] 1699. 제곱수의 합 https://www.acmicpc.net/problem/1699 처음에는 문제에 대한 접근을 일단 될 수 있는대로 큰 제곱수 (x [BOJ][DP] 11057. 오르막 수 문제 -> https://www.acmicpc.net/problem/11057 이번 문제는 나름 참신하게 문제를 푼 것 같다?..어떤 누군가가 이렇게 풀이를 한 사람이 있을수도 있겠지만.. ======================================== 보통 3중 for문으로 일일이 dp값을 다 더하는 반면에, 나는 연산량을 줄이려고 다른 점화식을 생각해봤다.. dp[i][j] : i번째 자릿수에서 숫자 j가 만들어낼 수 있는 경우의 수 여기서 만들어 낼 수 있는 경우의 수라고 함은 숫자 j가 i+1번째 자릿수의 가능한 경우의수를 의미한다. dp[i][10] : i+1번째 자릿수의 모든 경우의 수 i-1 번째 자릿수의 가능한 경우의 수는 i번째의 숫자 0이 만들 수 있는 경우의 수와 같으므로 d.. [BOJ][DP] 11053. 가장 긴 증가하는 부분 수열 문제 -> https://www.acmicpc.net/problem/11053 오래 생각을 해도 기존에 했던 생각밖에 들지 않고참신한 방법이 들지 않는다. 결국 또 참고하게 됬다..무엇이 문제일까. ============================================= DP에서 유명한 문제라고 한다. 일일이 내 뒤에있는 값을 신경쓰며 비교하고 지지고 볶고 할 필요 없이, 현재 자기 자신보다 작은 값이 가지고 있는 길이(dp값) 중 제일 큰 것을 자신을 포함해서 더하면 된다. 처음에는 모두 0이다.첫번째 값인 10은 자기 자신밖에 없으므로 1. 두번째 20은 자기 앞에 자기보다 작은 수인 10이 존재한다.고로 그 10의 길이인 1을 더한다. 세번째 10은 자기보다 작은 수가 없어 그냥 자기 길이.. [BOJ][DP] 2293. 동전 1 문제 -> https://www.acmicpc.net/board/view/10754 금방 풀릴 것 같은 예감과 함께즐겁게 생각을 했으나.. 역시나. 오래걸렸다..결국 풀이를 참고할 수밖에 없었고.. DP를 이제 나름 꽤 푼 것같은데 실력이 안느는것일까... 각설하고. 1 ~ 10원까지 세 가지 동전을 조합하여 나오는 경우의 수를 DP 배열에 넣고,그 DP를 이용하여 계속 10원까지 계산한다는 식의 접근 방법을많이 떠올렸을 것이라 생각한다. (내가 이랬다) 위의 경우 중복을 고려하여 일일이 다 빼줘야하는데,그럴경우 재귀로 구현해야한다. 쉽게 코드 몇줄로 이 문제를 풀 수가 있는데, 사용자가 입력한 값들중에서제일 작은 값을 최대한 활용하여 나머지 입력 값들에 대한경우의 수를 구해줘야 한다. 문제에 있는 예제.. [BOJ][DP] 9465. 스티커 문제 -> https://www.acmicpc.net/problem/9465 하나를 선택하면 상하좌우를 선택할 수가 없다. 그러면, 대각선으로만 추가적으로 계속 선택해나갈 수 있다는 말. 근데, 무조건 제일 근접한 대각선에 위치한 값만 가져와서는 안된다. 그 옆에있는 것도 고려를 해서 둘 중 큰 값을 골라야 한다.이런식으로 구상을 할 수가 있다. 점화식은 위 그림을 토대로 dp[0][i] = Max(dp[1][j-1], dp[1][j-2]) + dp[0][i];dp[1][i] = Max(dp[0][j-1], dp[0][j-2]) + dp[1][i];가 되겠다. 배열을 왜 한개만 썼냐면,굳이 두개를 쓸 필요없이 dp배열에 초기값을 넣고서이후 각각의 최댓값만 넣주면 더 이상 쓸 필요가 없기 때문이다. 소스(.. 이전 1 2 다음
