Hello Ocean! 🌼

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. => 연속하지 않아도 된다는 것이 포인트. 풀이 2차원 cache를 이용한 DP 방식으로 풀면 된다. 말로 풀어 쓴 것은 이해하기 힘드므로 그림을 그려보았다. s1 = ACAYKP s2 = CAPCAK 를 입력했을 때 cache의 모습이다. cache[i][j]에는 s1의 i 번째와 s2의 j 번째가 같을 때 값이 채워진다. (같지 않은 경우에는 0이 채워진다) 둘이 같을 때, 그냥 1을 채우는 것이 아니라 지난 구역에서 가장 큰 값+1을 채운다. 첫 번째 그림에서 빨..

[문제] 회전하는 벨트 위에 위와 같이 초밥들이 있다. 벨트 위에는 같은 종류의 초밥이 여러개 있을 수 있다. 손님은 초밥을 골라서 먹을 것이다. 1. 연속으로 k접시를 먹을 경우, 할인된 가격을 지불한다. 2. 각 고객에게 초밥 종류 중 하나가 쓰여진 쿠폰을 발행하고, 손님이 1번 행사에 참가할 경우 해당 초밥 1접시를 무료로 제공한다. 벨트 위에 해당 초밥이 없을 경우 새로 만들어 제공한다. 손님은 위의 행사에 참여하여 최대한 다양한 종류의 초밥을 먹으려고 한다. [input] 벨트에 놓인 접시의 수 N ( 2 ≤ N ≤ 30000 ) 초밥의 가짓수 d ( 2 ≤ d ≤ 3000 ) 연속해서 먹는 접시의 수 k ( 2 ≤ k ≤ 3000 (k ≤ N) ) 쿠폰번호 c ( 1 ≤ c ≤ d ) N d ..