목록다이나믹 프로그래밍 (63)

1일1알

백준 13703번 물벼룩의 생존확률 C++

https://www.acmicpc.net/problem/13703 13703번: 물벼룩의 생존확률 수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를 www.acmicpc.net 다이나믹 프로그래밍 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int k, n; vector c..
알고리즘 2023. 2. 2. 12:09
백준 16957번 체스판 위의 공 C++

https://www.acmicpc.net/problem/16957 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙 www.acmicpc.net 이미 지나간 길은 따로 저장해서 불필요한 계산은 줄이는 메모이제이션 기법을 활용하여 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace s..
알고리즘 2022. 12. 29. 11:33
백준 15990번 1, 2, 3 더하기 5 C++

https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 다이나믹 프로그래밍 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; const int64 mod = 1000000009; vector cache; int64 d..
알고리즘 2022. 11. 19. 12:43
백준 12869번 뮤탈리스크 C++

https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net dp #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n; vector v; vector cache; int ..
알고리즘 2022. 10. 22. 15:07
백준 1699번 제곱수의 합 C++

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net dp[n]의 최솟값은 dp[n - a^2] + 1 중 최솟값이다. (a^2 > n; vector dp(n + 1); for (int i = 1; i
알고리즘 2022. 10. 8. 12:02
백준 17404번 RGB거리 2 C++

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 첫번째 집을 빨강, 초록, 파랑 색으로 각각 지을 때 최솟값을 찾고 셋중에서 최솟값을 찾았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using name..
알고리즘 2022. 9. 30. 19:14
이전 Prev 1 2 3 4 5 ··· 11 Next 다음