[Softeer] 비밀메뉴2(Lv.3) - Day4

📋 개요 

2일차도 모든 문제를 풀어내고 다시 포스팅을 하면서 문제를 복기했다. 문제를 복기하는 것도 다시 한번 생각하게 되는 계기가 되어서 좋은거 같는 생각이 든다.

2024.01.29 - [Algorithm/Problem] - [Softeer] GBC(Lv.2) - Day3

2024.01.29 - [Algorithm/Problem] - [Softeer] 우물 안 개구리(Lv.3) - Day3

[Softeer] 우물 안 개구리(Lv.3) - Day3

[Softeer] GBC(Lv.2) - Day3

 

4일차도 Lv.3, Lv.2 문제로 나왔다. 이번에는 Lv.3가 첫번째 문제인데, 비밀메뉴2라는 문제이다. 전에 백준에서 최장 공통 부분 수열을 풀이한적이 있어서 이를 알고 있다면 문제를 푸는데 어려움을 없을거 같다는 생각이 든다.

https://softeer.ai/practice/6259

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

🧩 문제

회사 식당에는 전설처럼 전해 내려오는 비밀 메뉴에 대한 소문이 있다. 소문의 내용은 대강 이러하다.

식권 자판기의 버튼을 특정 순서대로 누르고 결제를 하면, 평소와는 다른 색깔의 식권이 나온다. 이 식권을 배식대에 제출하면, 어떤 비밀 메뉴를 받을 수 있다는 것이다.

물론 이를 실제로 본 사람은 아무도 없어서, 어떤 메뉴가 나오는지는 커녕 눌러야 하는 버튼의 순서조차 알려져 있지 않다.

 

식당의 평범한 이용객인 당신은 이 소문을 들은 순간 비밀 메뉴에 호기심이 생겼다. 그 실체를 쫓아 연구를 거듭한 지도 어언 몇 달째. 당신은 자판기의 버튼을 아무렇게나 두들기면서, 비밀 메뉴가 나오는 조작법을 두 가지 찾아냈다!

 

당신은 이 두 조작법을 연구해 비밀 메뉴 조작법을 찾고자 한다.

 

당신은 버튼에 1 이상 K 이하의 정수로 된 번호를 매겨, 이러한 숫자의 나열로 버튼 조작을 표현했다. 당신의 직감은 둘 모두에 포함된 일련의 조작법 중 가장 긴 것을 찾아야 한다고 말하고 있다.

일련의 조작법이란, 나열된 숫자들에 존재하는 연속된 부분 수열을 의미한다.

 

길이가 각각 N과 M인 버튼 조작 과정이 주어질 때, 둘 모두에 완전히 포함되는 일련의 조작 과정 중 가장 긴 것의 길이를 출력하여라.

⛔ 제약조건

1≤N≤3,000

1≤M≤3,000

1≤K≤1,000,000

각 버튼의 번호는 1 이상 K 이하이다.

📝  형식 

📥 입력	📤 출력
첫째 줄에 N, M, K가 공백을 사이에 두고 주어진다. 둘째 줄에 첫 번째 버튼 조작을 나타내는 N개의 정수가 공백을 사이에 두고 주어진다. 각 정수는 1 이상 K 이하이다. 셋째 줄에 두 번째 버튼 조작을 나타내는 M개의 정수가 공백을 사이에 두고 주어진다. 각 정수는 1 이상 K 이하이다.	비밀 메뉴 조작법으로 가능한 가장 긴 것의 길이를 첫째 줄에 출력한다. 만일 겹치는 조작이 전혀 없다면 0을 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1		2
2		4
3		0

🖥️ 내 코드

---

📖  해설 및 느낀점

# LCS (최장 공통 부분 수열)

Longest Common Subsequence의 약자로써 쉽게 말해 가장긴 공통된 부분 수열을 이야기하는 것이다. 이는 Dynamic Programing의 대표 유형이라고 볼 수있다. 위에 작성된 코드를 예제1에 기반하여 표로 나타내보았다.

 

매트릭을 만든후에 만들어진 매트릭을 전체 0으로 초기화를 진행하고 수열이 연속될때마다 카운트를 하나씩 증가하는것이다. 사실 LCS는 dp에서 자주 나오는 문제라 문제 유형자체를 암기하고 있으면 좋을거같다.

 

문제를 푸는데 큰 어려움은 없었다. 이미 백준에서도 관련된 문제를 몇개 풀어보았기 때문....! 백준에도 있다는 것은 그만큼 많이 나온다는 것이다.

 

LCS는 matirx를 통해 dp해서 푼다는 것만 기억하자.