DP16 [C/C++] 11052: 카드 구매하기 문제를 Top-down 방식으로 이해해본 다음에 Bottom-Up 방식으로 구현을 하였다. 예를 들어 dp[n]을 구하는 경우에 dp[n]=max(dp[n]+dp[0],dp[n-1]+dp[1],dp[n-2]+dp[2],,,,,,,,,,dp[n-k]+dp[k],,,,) 형태가 된다는 것을 알 수 있다. 이때 dp[n-k]와 dp[k]일때 (n-k>=k) 최대값을 각각 구하고 있다면 dp[n-k]+dp[k]도 최댓값이 된다. 따라서 k=1에서 k=[n/2]인 자연수까지 중에서 최댓값을 구한다면 dp[n]을 구할 수 있게 된다. 그 결과 dp[1]부터 dp[n]까지 각 경우의 최댓값을 dp배열에 저장하고 이를 이용해 문제를 풀었다! 이걸 비교하는 코드는 아래와 같다. for(int i=2;i=j) { dp[i.. 2023. 8. 30. 11727: 2Xn 타일링 2 이 문제도 타일링 1문제와 같이 점화식만 찾으면 쉽게 풀 수 있다. dp[i-2]에서와 dp[i-1]에서 각각 길이가 2개짜리와 1개짜리를 더했을때 나오는 경우의 수를 구하여 점화식을 만들어보면 dp[i]=dp[i-1]+dp[i-2]+dp[i-2]가 된다. 점화식을 풀 때 dp[1]부터 하나하나 해보면서 구하는 것도 좋지만 dp[i]일때부터 생각해서 일반적인 해의 풀이를 구하는 것이 이 문제에서는 점화식을 더 찾기 쉬운 경우이다. i-1 덩어리와 i-2 덩어리가 있을 때 i짜리 덩어리를 만들기 위한 경우의 수를 구하면 된다. #include int dp[1001]; int main(void) { int n; scanf("%d",&n); dp[1]=1; dp[2]=3; dp[3]=dp[1]*dp[2]+dp.. 2023. 7. 29. [C] 11726: 2Xn 타일링 생각보다 쉽게 풀려서 깜짝 놀랐다 아무래도 평소에 조금 더 어려운 문제를 푸느라 상대적으로 쉽게 느껴졌나보다! 아무래도 점화식도 피보나치 수열과 같은 형태라 생각이 떠올리기 쉬웠고 점화식형태도 하나라서 직관적으로 보였다. 무엇보다 구현도 간단했는데 다만 주위해야할건 입력값이 1000개인데 피보나치 수열의 특성상 f(1000)은 int의 범위에서 벗어난다. 아마 long long int를 써도 벗어날 것 이다, 따라서 이때 생각났던 문제가 nCr, 조합 관련 문제였는데 이것도 n!이 n이 커질수록 기하급수적으로 커지기 때문에 n-i를 곱할때 i만큼 동시에 나눠져야 범위를 벗어나지 않는다. 이것도 마찬가지로 10007을 넘어갈 때마다 10007로 나눈 나머지를 dp[]에 넣어주면 된다. 다음은 아래 소스코드.. 2023. 7. 25. [C] 2156: 포도주 시식 처음에 점화식을 쉽게 찾았고 구현도 다른 DP 문제처럼 쉽게 되서 완전 쉽게 풀줄 알았다... 점화식은 쉽게 보면 근데 여기서 간과한 점이 다른 "계단 오르기"문제와의 차이점이 있다는 것인데 그건 바로 와인을 안마셔도 된다는 것이었다..! 예를 들어 (6) 100 100 1 1 100 100의 최대 포도주 양은 계단 오르기 문제에서는 301이지만 여기서는 400이 된다. 3번째와 4번째에서는 안마시는게 이득이다. 따라서 if(dp[i]=2) { dp[2]=dp[1]+arr[2]; cnt=2; //연속 두잔을 마심 max=dp[2]; } if(n==3) { if(arr[2]>arr[1]) dp[3]=arr[2]+arr[3]; else { dp[3]=arr[1]+arr[3]; cnt=1; } max=dp[3.. 2023. 7. 24. 이전 1 2 3 4 다음
