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

1일1알

백준 2705번 팰린드롬 파티션 C++

1. 자기 자신도 팰린드롬 파티션이기때문에 dp배열을 1로 초기화한다. 2. 0 ~ i - 1 까지 i 에서 뺀 값이 짝수이면 2로 나눠서 양쪽으로 배치해서 팰린드롬 파티션으로 만들 수 있기 때문에 dp[(i - 뺀 값) / 2] 를 dp[i]에 더해준다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector ..
알고리즘 2022. 2. 13. 12:08
백준 2225번 합분해 C++

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. dp테이블을 dp[n][k]라고 하고, k개의 수로 n을 만들 수 있는 경우의 수 라고 하였다. 의외로 간단하게 해결할 수 있다. 예를 들어 dp[3][4]는 4개의 수로 3을 만들 수 있는 경우의 수인데, 마지막에 0이 온다면 3개의 수로 3를 만드는 경우의 수, 마지막에 1이 온다면 3개의 수로 2을 만드는 경우의 수, 마지막에 2가 온다면 3개의 수로 1를 만드는 경우의 수, 마지막에 3이 온다면 3개의 수로 0을 만드는 경우의 수 이다. 이 경우들을 모두 합하면 되기 때문에 점화식은 dp[n][k] = dp[n][k-1] + dp[n-1][k-1] + dp[n-2][k-1] + .... dp[0][k-1] 이다. 그리고 테이블을 채워가다 보면 dp..
알고리즘 2022. 1. 2. 12:24
백준 10835번 카드게임 C++

오른쪽 카드가 왼쪽 카드보다 작은 경우와, 큰 경우 두 가지로 나누어서 문제를 해결하였다. 오른쪽 카드가 왼쪽 카드보다 작은 경우는 1. 오른쪽 카드의 점수를 얻고 오른쪽 카드를 빼는 경우 2. 왼쪽 카드를 빼는 경우 3. 양쪽 카드를 빼는 경우 이 세 가지 중 큰 값을 구했고 반대의 경우에는 1. 왼쪽 카드를 빼는 경우 2. 양쪽 카드를 빼는 경우 이 두 가지 중 큰 값을 구했다. 그리고 같은 지점을 계속 탐색할 수 있기 때문에 시간 초과나 스택 오버플로우가 발생할 수 있다. 그렇기 때문에 메모이제이션 기법을 통해 dp배열에 방문한 곳을 저장해서 바로 빠져나올 수 있게 작성하였다. #include #include #include #include #include #include #include #incl..
알고리즘 2021. 12. 22. 13:03
백준 15486 퇴사 2 C++

다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 상담을 하는데 걸리는 시간이 있기 때문에 상담을 시작한 시간이 아닌, 상담이 끝난 시간을 기준으로 점화식을 세워야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector v(n + 1, { 0,0 }); vector dp(n + 1, 0); ..
알고리즘 2021. 12. 18. 14:37
백준 16194번 카드 구매하기 2 C++

https://kjhcocomi.tistory.com/11 백준 11052번 카드 구매하기 C++ 한정된 공간 안에 최대한의 가치를 넣는 배낭 채우기와 비슷한 문제이다. 카드의 개수가 무게, 가격을 가치라고 생각하면 된다. 하지만 한가지 다른 점이 있는데, 한 종류의 카드팩을 여러번 살 kjhcocomi.tistory.com 이 문제와 유사한 문제이다. 금액의 최대가 아닌 최솟값을 구하면 된다. 여기서는 최솟값을 구해야 하기 때문에 초기값을 넣어주어야 한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; t..
알고리즘 2021. 12. 17. 12:18
백준 1495번 기타리스트 C++

2차원 dp테이블 dp[n][m]을 이용해서 n에는 현재 곡의 번호, m은 볼륨 정보로 가능한지 가능하지 않은지 여부를 통해 dp테이블을 채우고, 마지막 곡에서 가장 큰 m의 값이 정답이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, s, m; vector volumes; int volume; int ans = -1..
알고리즘 2021. 12. 16. 13:28
이전 Prev 1 ··· 4 5 6 7 8 9 10 11 Next 다음