본문 바로가기

DP37

AtCoder ABC 265 풀이 A. 1개살때 X원, 3개살때 Y원이 들때 N개살때 최소비용을 구하는 문제입니다. 우선, Y가 3X이상이면 그냥 다 1개씩 사면 됩니다. 그 외의 경우엔 3개씩 최대한 묶고 남은걸 1개씩 사주면 됩니다. #include using namespace std; int main() { ios::sync_with_stdio(0), cin.tie(0); int x, y, N; cin >> x >> y >> N; if (y >= 3 * x) { cout n >> m >> t; for (int i = 1; i > a[i]; psum[i + 1] = psum[i] + a[i]; } ll time_limit = t; x[0] = 1; for (int i = 1; i > x[i] >> y[i.. 2022. 8. 25.
백준 3037 / C++ https://www.acmicpc.net/problem/3037 3037번: 혼란 첫째 줄에 혼란도가 C이고 길이가 N인 수열의 개수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net [ 풀이 ] dp[i][j]를 1~i까지 혼란도가 j인 수열의 개수라고 정의하자. 1~i번 칸에서 수 i를 놓는 위치를 생각해보자. i를 k번 칸에 놓았다면, k+1칸~i번 칸에 의해 혼란도가 i-k개 증가한다. 따라서 i를 k번 칸에 놓을 때 혼란도가 j가 되려면 k번칸을 제외한 1~i-1에서 혼란도가 j-(i-k)가 되어야 한다. 따라서 식은 dp[i][j]=sum(dp[i-1][j-i+k])이다. 식을 더 개선해보자. dp[i][j]와 dp[i][j-1] 차를 구하면, dp[i-1][.. 2022. 8. 22.
백준 1866 / C++ https://www.acmicpc.net/problem/1866 1866번: 택배 첫째 줄에 배송해야 할 물품의 개수 N이 주어진다. (1 ≤ N ≤ 3,000) 둘째 줄에는 각 물품의 목적 지점의 번호가 빈 칸을 사이에 두고 주어진다. 지점의 번호는 10,000 이하의 자연수이다. 셋째 줄에 www.acmicpc.net [ 풀이 ] 관찰을 통해 인접한 값들끼리, 그리고 그 거리들이 멀수록 헬기로 옮기는게 좋음을 알 수 있다. 정렬한 후 앞에서부터 트럭으로 옮길지 헬기로 옮길지 정해주자. 또한 옮기는 위치도 결정해줄 수 있다. d1, d2 , .... , di를 골라서 옮겼다고 할 때 헬스가 x지점에 내려주면 트럭으로 움직여야 하는 거리는 f(x)=sum(|x-d_i|)가 된다. 이 함수는 중간지점에서.. 2022. 8. 18.
백준 5463 / C++ https://www.acmicpc.net/problem/5463 5463번: 건포도 플로브디브의 유명한 초콜릿 가공업자 Bonny는 가로 M개, 세로 N개의 격자에 건포도들이 들어있는, N*M크기의 건포도 초콜릿을 만들었다. 각 1*1 격자에는 최소 1개 이상의 건포도가 들어있으며, 2개 www.acmicpc.net [ 풀이 ] 나눴을 때 합을 계산해주려면 시작점 좌표와 끝점 좌표를 알아야 한다. 마침 n,m도 50이하다. dp[sx][sy][ex][ey]를 (sx,sy)~(ex,ey)로 만들어지는 직사각형에서 건포도의 최소 양이라고 하자. 전이는 2가지다. 가로로 자르는 경우, 세로로 자르는 경우. 이후 식을 세우는건 쉬우므로 코드로 대체한다. [ Code ] #include using namespa.. 2022. 8. 17.