본문 바로가기

동적 계획법34

[백준] 10803번 정사각형 만들기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 정사각형 만들기 https://www.acmicpc.net/problem/10803 10803번: 정사각형 만들기 두 변의 길이가 모두 양의 정수인 직사각형 모양의 종이가 주어져 있다. 이 종이를 칼로 여러 번 잘라서 모든 조각이 한 변의 길이가 양의 정수인 정사각형이 되도록 하고자 한다. 칼로 종이를 www.acmicpc.net 쉬운 DP문제일 줄 알았으나, TLE에서 최적화하느라 꽤 걸린 문제였습니다. (i)의 방법으로 1~n/2, 1~m/2까지 자릅니다. 하지만 큰 수에서 O(n*m)의 연산이 필요하기 때문에 큰 수에서는 (ii) 방법을 이용하여 최소 정사각형 개수를 구합니다. C++ 소스코드) Full Code) https://github.com/Chocochip1.. 2021. 12. 20.
[백준] 16194번 - 카드 구매하기 2 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 카드 구매하기 2 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net Top-down 방식으로 풀이 했습니다. DP 모델링을 res카드를 구매하기 위해 지불해야하는 최소 금액으로 memoization을 진행했습니다. 풀다가 P의 범위를 i=0으로 지정해서 꽤 걸렸네요ㅜㅜ C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%.. 2021. 12. 3.
[백준] 15990번 - 1, 2, 3 더하기 5 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 1, 2, 3 더하기 5 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 이전 사용한 숫자(prev)를 memoization하여 prev를 제외한 숫자를 사용하여 합을 나타낼 수 있는 방법을 계산한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/15990_1%2C%202%2C%203%20%EB%8D%94%ED%95%98%EA%.. 2021. 11. 13.
[백준] 7579번 - 앱 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 메모리를 memoization을 진행하면 메모리 초과로 터진다. dp[idx][Cost]: Cost로 idx번째 앱에서 얻을 수 있는 최대 메모리를 계산한다. Cost를 0부터 증가시켜 M보다 클 경우 break 하여 출력한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main.. 2021. 11. 7.
[백준] 11060번 - 점프 점프 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 점프 점프 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net cache[idx]: idx에서 n-1번 칸까지 갈 수 있는 최소 점프 횟수. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/11060_%EC%A0%90%ED%94%84%20%EC%A0%90%ED%94%84.c.. 2021. 11. 4.
[백준] 9507번 - Generations of Tribbles (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - Generations of Tribbles https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net n이 3 이하 일 경우의 기저 사례 처리와 점화식을 이용해 memoization을 적용한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/9507_Generations%.. 2021. 11. 3.
[백준] 14728번 - 벼락치기 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 벼락치기 https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 한정된 시간에 최대 점수를 내기 위해 선택해야하는 전형적인 냅색(배낭) 문제. DP(인덱스, 남은 공부 시간)으로 해결할 수 있다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999.. 2021. 11. 2.
[백준] 2056번 - 작업 (C++) 문제 및 풀이 문제) 백준 - 위상 정렬 & DP - 작업 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상 정렬 아이디어와 DP를 이용하여 풀 수 있는 문제. ACM Craft문제와 비슷하여 그렇게 풀려고 했지만, Top-Down으로 푸는 거 포기... n번째 사람까지 걸리는 작업 시간을 memoization 하면 된다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blo.. 2021. 10. 1.
[백준] 4811번 - 알약 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 알약 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net cache[w][h]: 약 w(한 조각), h(반 조각)의 개수 memoization solve(w, h): top-down방식으로 알약 한 조각 먹을수 있는 경우(w > 0), 반 조각 먹을 수 있는 경우(h > 0)를 더해서 return C++ 소스코드) Full code) https://github.com/Chocochip101/BO.. 2021. 9. 29.
반응형

티스토리툴바