DP23 [백준] 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. [백준] 12852번 - 1로 만들기 2 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 1로 만들기 2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net Top-Down 방식으로 해결했다. 1로 만들수 있는 모든 경우를 memoiztion을 진행하면서 trace에도 memo를 진행한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/12852_1%EB%A1%9C%20%EB%A7%8C%EB%93%A4%EA%B8%B0%202.cpp GitHub - Chocochip101/BO.. 2021. 11. 6. [백준] 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. [백준] 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. [백준] 5557번 - 1학년 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 1학년 -> https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net F (Idx, PartialSum) : 0번째 수부터 Idx까지의 합의 개수 DP에 적용할 점화식을 다음과 같다고 하자. 그럼 점화식을 F(Idx + 1, PartialSum + number[Idx + 1]) + F(Idx + 1, PartialSum - number[Idx + 1])로 통해 올바른 등식의 .. 2021. 7. 27. [백준] 2186번 - 문자판 (C++) 문제 및 풀이 문졔) 백준 - 동적 계획법 (Dynamic Programming) - 문자판 -> https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net F(x, y, index): 점 (x, y)에서 index이후의 부분 문자열을 만들 수 있는 경로의 개수 점화식을 다음과 같이 설정 후, 모든 문자판을 순회하면서 F(x, y, index)의 값을 더한다. C++ 소스코드) 2021. 7. 27. [백준] 1563번 - 개근상 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 개근상 -> https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net cache[ i ][ j ][ k ]를 길이가 i이고 지각(L)이 j번이면서 끝문자의 연속 결석 회수가 k번으로 정의한다. 가령, 'LOAA'는 cache[4][1][2]의 한 요소이고, 'OALAO'는 cache[5][1][0]의 한 요소이다. 결석은 세번 연속으로 하지 않는 이상 개근상에 영향을 주지 않기 때문에 끝에 연속된.. 2021. 7. 6. 이전 1 2 3 다음 반응형
