본문 바로가기

Dynamic Programming17

[C/C++] 백준 17404: RGB 거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 하나 주의해야 할건 첫번째 칠한 집과 마지막으로 칠한 집의 색깔이 같으면 안되는것이다. 그렇기 때문에 기존의 DP로 문제를 풀게 된다면 이 조건을 만족시키기에 쉽지 않다. 따라서 여기서 생각해야하는건 첫번째로 칠할 집의 색깔을 정하고 나서 for문을 3번 돌며 각각의 경우세어 모든 집을 칠하는 비용의 최솟값을 구해야한다. 즉 dp[0][1]로 시작했을 때는 dp[1][.. 2023. 9. 28.
[C/C++] 11057: 오르막 수 최대한 점화식을 구하려고 생각하다보니 규칙을 발견하게 됐다! 다른 DP 문제와는 다르게 2차원 배열을 이용하여 DP를 저장해야지 풀려서 생각하는데 조금 시간이 걸린 것 같다. dp[n][n]에서 첫번째부터 생각을 해보면 dp[1]=1 1 1 1 1 1 1 1 1 1 => 10 dp[2]=10 9 8 7 6 5 4 3 2 1 => 55 dp[3]=55 45 36 28 21 15 10 6 3 1 => 220 . . . 이런 식으로 나아가는데 dp[i]와 dp[i-1]간의 관계를 살펴보면 dp[i][1]=dp[i][10]이고 dp[i][2]=dp[i][1]-dp[i-1][1] dp[i][3]=dp[i][2]-dp[i-1][2] . . 이런 식으로 나아간다. 따라서 이렇게 쭉 뻗어나가면 점화식을 얻을 수 있다... 2023. 8. 30.
[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.
[C/C++] 17626: Four Squares 일단 bruteforce하게 구현한 코드이다.(굳이 말하면 dp를 조금 이용하여 계산 수를 줄임) 먼저 제곱수는 최소 개수의 제곱수의 합이 1이므로 먼저 dp배열에 저장해준다. 최소개수의 제곱수의 합이 2인 수들은 최소 개수의 제곱수의 합이 1인 수 2개의 합이므로 MakeContinue 함수를 이용해 구하고 최소개수의 제곱수의 합이 3인 수들은 최소 개수의 제곱수의 합이 1인 수와 최소 개수의 제곱수의 합이 2인 수들의 합이므로 이를 이용해서 구하면 된다. 그리고 마지막으로 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으므로 dp[i]==0인 경우에 최소개수의 제곱수의 합이 4인것을 알 수 있다. #include #include int dp[100001]; //int tmp=cpy_o.. 2023. 8. 22.

티스토리툴바