동적 계획법34 [백준] 11568번 - 민균이의 계략 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 민균이의 계략 https://www.acmicpc.net/problem/11568 11568번: 민균이의 계략 민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 www.acmicpc.net 11053번 - 가장 긴 증가하는 부분 수열 문제와 같은 문제입니다. 현재 idx에서 만들 수 있는 가장 긴 부분 수열의 길이를 memoization하여 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/11568_%EB%AF%BC%EA%B.. 2022. 3. 11. [백준] 14430번 - 자원 캐기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 자원 캐기 https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net 현재 칸에서 오른쪽, 아래쪽으로 갔을 때 얻을 수 있는 최대 광석 수를 동적 계획법을 통해 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/14430_%EC%9E%90%EC%9B%90%EC%BA%90%EA%B8%B0.c.. 2022. 3. 4. [백준] 15486번 - 퇴사 2 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 퇴사 2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net N이 150만이기에 동적 계획법으로 해결이 안 될 줄 알았는데 생각보다 넉넉한 시간에 통과해서 의외였습니다. solve(now)를 통해 해당 날짜에서 얻을 수 있는 최대 수익을 계산합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/S.. 2022. 2. 28. [백준] 21317번 - 징검다리 건너기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 징검다리 건너기 https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 전형적인 동적 계획법으로 쉽게 해결할 수 있는 문제였습니다. solve(i, usedMegajump)를 통해 i 번째 돌까지 갔을때 필요한 최소 에너지의 memoization을 통해 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/21317_%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%EA%B1%B4%EB%84%88%EA%B8%B0.cpp .. 2022. 2. 23. [백준] 2302번 - 극장 좌석 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 극장 좌석 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net VIP 좌석을 제외한 연속된 i개 자리에 대하여 피보나치 수열 i개로 사람들을 앉힐 수 있습니다. 동적 계획법을 통해 피보나치 수를 구하고 입력으로 들어온 VIP 좌석마다 ans에 곱합니다. C++ 소스코드) 2022. 2. 18. [백준] 1633번 - 최고의 팀 만들기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 최고의 팀 만들기 https://www.acmicpc.net/problem/1633 1633번: 최고의 팀 만들기 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플 www.acmicpc.net 동적 계획법을 통해 해결했습니다. solve(int idx, int b_cnt, int w_cnt) 함수는 idx번째 사람까지 고른 흑(b_cnt)과 백(w_cnt)을 골랐을 때, 능력치의 최댓값입니다. solve 함수 내에서 idx번째 사람을 뛰어넘거나 흑 플레이어로 추가하거나 백 플렉이어로 추가합니다. C++ 소스코드) Full Code.. 2022. 2. 12. [백준] 22869번 - 징검다리 건너기 (small) (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 징검다리 건너기 (small) https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 0번째부터 오른쪽으로 출발하여 N-1번째까지 도착할 수 있는지 확인합니다. cache[idx]를 통해 idx번까지 도달 여부를 저장해 1일 경우 가능, -1일 경우 미방문, 0일 경우 불가능으로 판단합니다. C++ 소스코드) Full Code) https://github.co.. 2022. 2. 8. [백준] 2602번 - 돌다리 건너기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 돌다리 건너기 https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 두루마리 문자열의 인덱스, 다리의 인덱스, 악마/천사 여부를 이용하여 현재 위치에서 돌다리를 건널 수 있는 모든 경우를 동적 계획법을 이용해 계산합니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/2602_%EB%8F%8C%EB%8B.. 2022. 2. 4. [백준] 2629번 - 양팔저울 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 추의 인덱스와 한쪽 저울에 올린 무게를 memoization을 적용하여 동적 계획법을 진행합니다. 추를 올릴 경우, 추를 올리지 않을 경우, 반대쪽에 올릴 경우를 생각하여 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/26.. 2022. 1. 15. 이전 1 2 3 4 다음 반응형
