동적계획법5 [백준] 13302번 - 리조트 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 리조트 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 날짜와 쿠폰의 개수를 memoization하여 문제를 해결합니다. 쿠폰, 하루권, 3일권, 5일권을 각각 사용할 경우의 최소비용을 구합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/13302_%EB%A6%AC%EC%A1%B0%ED%8A%B8.cpp GitH.. 2022. 3. 18. [백준] 10653번 - 마라톤 2 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 마라톤 2 https://www.acmicpc.net/problem/10653 10653번: 마라톤 2 젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다. www.acmicpc.net 모든 체크 포인트의 좌표를 입력 받아 거리를 미리 계산합니다. 그 후, 체크 포인트를 뛰어넘는 경우와 그렇지 않는 경우로 각 최소 거리를 계산합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/10653_%EB%A7%88%EB%9D%BC%ED%86%A4%202... 2022. 1. 17. [백준] 5582번 - 공통 부분 문자열 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net LCS랑 유사한 연속된 공통 문자열을 찾는 문제였습니다. LCS를 풀어봤다면 쉽게 풀 수 있는 문제입니다. C++ 소스코드) 2021. 12. 22. [백준] 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. [백준] 10422번 - 괄호 (C++) 문제 및 풀이 문졔) 백준 - 동적 계획법 (Dynamic Programming) - 괄호 -> https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 괄호의 길이가 L인 올바른 문자열의 개수를 구하고자 할 때, L은 다음과 같이 구할 수 있다. solve(n)를 길이가 n인 올바른 문자열의 개수라 하면, 위의 문자열에서는 solve(L) = ∑ {solve(i - 2) * solve(L - i)}임을 알 수 있다. 또한, solve(i - 2)를 구하기 위한 작.. 2021. 6. 29. 이전 1 다음 반응형
