본문 바로가기

ALGORITHM/DP

 (4)
[Swift] 5582 공통 부분 문자열 (DP) https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 생각 처음엔 contains 함수를 사용하여 일일이 길이를 구했는데 시간초과가 났다. 시간을 줄이기 위해서 DP를 사용 풀이 만약 [i]와 [j]의 알파벳이 같다면 [i-1][j-1] 까지의 공통 부분 길이에서 1을 더해주고 저장한다. 같지 않다면 0이다. A B R R 0 0 1 A 1 0 0 B 0 2 0 전체코드 import Foundation let str1 = Array(rea..
[c++] 7579 앱 (knapsack) https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 노트북 재부팅 5번의 원인이 된 문제 이유는.. 1 ≤ m1, ..., mN ≤ 10,000,000을 만족한다. 또한, 0 ≤ c1, ..., cN ≤ 100이고, M ≤ m1 + m2 + ... + mN 이래서 배열을 dp[101][1000000001] ㅋㅋㅋ이렇게 설정했더니 컴퓨터가 바로 종료.. 배열을 너무 큰 값으로 설정하면 안된다 그냥 비용을 dp 로 설정하면 되는 문제였다. 평소와 거꾸로 생각..
2156 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 점화식을 찾자 찾은 경우의 수는 세가지 각각 dp[i-3] + drink[i-1] + drink[i]; dp[i-2] + drink[i]; dp[i-1]; 세가지 중 가장 큰 값이 정답이 된다. 전체코드 #include #include using namespace std; int n, drink[10001], dp[10001], max_drink = 0; int main(int argc, const..
9095 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net DP와 친해지고자 풀었는데 예전에 풀었던 문제였다. DP에 대해 아는 것이라곤 점화식을 구하는 것 뿐.. 화이팅! #include #include using namespace std; int T, n, dp[11]; int main(int argc, const char * argv[]) { dp[1] = 1; dp[2] = 2; dp[3] = 4; for (int i=4; i> T; while(T--) { cin >> n; cout

티스토리툴바