[백준] 9251번 LSC (C)

문제 주소 백준 9251번 LSC 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 알고리즘 DP 힌트 첫번째 문자열의 i번 문자까지의 문자열과 두번째 문자열의 j번 문자까지의 문자열의 LCS의 길이를 구한다. 문제풀이 dp[i][j]에 문자열 a의 i번 문자까지의 문자열과 문자열 b의 j번 문자까지의 문자열의 LCS의 길이를 저장한다. 가장 끝의 문자만 비교하는 식으로 길이를 구해나갈 수 있다. 끝 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]+1 끝..

• format_list_bulleted Dynamic Programming
• · 2020. 4. 21.
• textsms

[백준] 2565번 전깃줄 (C)

문제 출처 한국정보올림피아드 지역본선 2007 초등부 4번 문제 주소 백준 2565번 전깃줄 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 알고리즘 DP 힌트 서로 교차하지 않는 전깃줄의 최대 개수를 구한다. 문제풀이 서로 교차하지 않는 전깃줄의 최대 개수를 구하기 위해선 한 쪽 전봇대 기준으로 정렬을 한 뒤 나머지 전봇대의 번호에서 가장 긴 증가하는 수열을 구하면 된다. #include ..

• format_list_bulleted Dynamic Programming
• · 2020. 4. 12.
• textsms