https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net DP로 해결했습니다. dp[i][j] 를 문자열 A를 i번 인덱스까지 자르고, 문자열 B를 j번 인덱스까지 잘랐을 때 두 문자열의 공통 접미사의 길이 로 정의한다. 이제 이 dp 배열을 O(N^2) 로 순회하면서 채우는데, 만일 A[i] 와 B[i]가 서로 같다면 A[i-1]과 B[i-1] 도 서로 비교해 보아야 한다. 이때, dp[i-1][j-1] 이 공통 접미사의 길이를 이미 저장하..
https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net DP 사용해서 해결했다. dp[i] 를 i일째 시점에서 상담을 끝냈을 때의 최대 이익으로 정의한다. i일째에 상담을 진행한 경우는 dp[i+T[i]] 를 dp[i] + P[i] 로 갱신 할 수 있으며, 이때 편의상 T[i]와 P[i] 를 0부터 시작하는 인덱스로 관리해주면 소스코드가 깔끔해진다. 상담을 진행하지 않더라도, 지난 일자에서의 최대 수익을 그대로 가져와서 ..
https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net DP 문제 ( 수열의 유도 및 구현 ) 개념을 알고 모르고의 유무로 난이도가 극명하게 갈린다고 할 수 있는 문제. 이 문제에서 요구하는 수열은 "교란순열" 혹은 "완전순열" 이다. 44라는 숫자가 나오면 한번쯤 의심해볼만할듯. dp[i] = (dp[i-1]+dp[i-2])*(i-1) 교란순열을 구하는 DP 점화식은 다음과 같다. DP[i] : i명끼리 조건에 맞게 선물을 분배하는 경우의 수 유도 각각의 사람의 번호를 $a_i$ , 선물의 번호를 $b_i$ 로 둔다. 어떠한 사람 A가 선물을 하는 경우는 $(N-1..
https://www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net 편집거리를 계산해내는 문제. PHP levenstein() 함수를 써먹고싶어지는 문제다 "편집 거리" 로 표현해 두었지만, 실제로 정확한 용어는 levenshtein distance 이다. 처음 발견한 사람이 레벤슈타인 이었나 보다. 위키피디아에서의 레벤슈타인 거리의 정의는 아래와 같다. 해당 점화식을 해석해서 DP로 기술할수 있는 분들은 건너뛰셔도 된다. 레벤슈타인 거리는 보통 O(N^2) DP로 해결하게 되는데, 두 문자열을 A, B라고 할때 DP[i][j]..
https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net DP 문제. DP[i] 를 버튼을 i번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값으로 만든다. DP[i] 의 기초 값은 DP[i-1] + 1 이다. ( 1번 버튼 화면에 A를 출력한다를 사용 ) 2, 3, 4번 연산은 사실상 한 세트라고 생각하면 되는데, 어..
https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net DP 문제. DP[i] 를 i번 색종이를 제일 위에 쌓을때 최대 장수로 정의한다. dp[i]를 구하는 방법은 i번 색종이 밑에 놓일 수 있는 보다 큰 색종이 k에 대한 dp[k] 와 비교를 해서, dp[i] = max(dp[i], dp[k]+1) 식으로 계산해주면 된다. 이때, k를 보다 빨리 찾고 편하게 비교하기 위해서, 입력으로 받는 색종이를 일괄적으로 가로 / 세로로 방향을 고..