이번에는 코드업 2699번 문제를 해결해 봅시다.

알고리즘에 대해 구상을 해봅시다.

배열에 탐색 시작부터 지금까지 공통적으로 몇개의 문자가 공통인지를 arr 배열에 저장하게 됩니다. 이러한 방식으로 끝까지 탐색을 마치면 arr의 끝에 총 공통 부분이 얼마인지를 보여주게 됩니다. 약간 경우의 수 구하는것과 느낌이 비슷하네요..
그럼 코드를 봐봅시다.
#include <stdio.h>
#include <string.h>
int arr[1001][1001]; //공통 문자열 길이 저장 배열
int max(int a,int b){ //둘중 큰값이 무엇인지 반환하는 함수
return a>b? a:b;
}
int main() {
char s1[1001],s2[1001];
scanf("%s %s",s1,s2); //문자열 두개 입력
int len1= strlen(s1); //문자열 길이
int len2= strlen(s2);
for(int i=1;i<=len1;i++){ //문자열 탐색
for(int j=1;j<=len2;j++){
if(s1[i-1]==s2[j-1]) arr[i][j]= arr[i-1][j-1]+1; //조건에 따라 arr배열 채우기
else arr[i][j]=max(arr[i-1][j], arr[i][j-1]);
}
}
printf("%d", arr[len1][len2]); //공통 문자열 길이 출력
}
처음에
arr[i][j]=max(arr[i-1][j], arr[i][j-1]);
이 부분에서 어떤 연산을 해주어야 할지 고민이 많았는데 수학 시간에 배웠던 것 같은 경로의 경우의 수를 구하는 문제가 생각 났습니다. 그래서 arr의 이전 열, 혹은 행 중 큰 숫자가 지금까지 탐색 중 공통부분 중 긴 부분이겠구나 라고 생각하여 함수를 만들어 사용하게 되었습니다. 이렇게 어렵던 부분이 해결되니 속이 뻥 뚤리는 기분이었습니다.
코드는 별로 길지 않아 보이지만 구현할때 많은 고민이 있었고 구현된 코드를 보아도 이해하기 어려울 수 있겠다라고 생각이 드네요.. 제 설명이 좋지 못한점을 사과드리고.. 앞으로 더 많은 게시물로 찾아 뵙겠습니다.

'AP 프로그래밍' 카테고리의 다른 글
12. codeup 2601 : 피보나치 수열 문제 해결 (0) | 2023.06.05 |
---|---|
9. codeup 2641 : 숏다리의 계단 오르기 (Small) 문제 해결 (0) | 2023.05.28 |
8. codeup 2608 : 동아리 회장 선거 문제 해결 (0) | 2023.05.28 |
5. codeup 2062 : Up 2 문제 해결 (0) | 2023.04.03 |
2. codeup 2834 : [상태 정의를 통한 탐색] 계단 오르기 3-1 & 2836 : [상태 정의를 통한 탐색] 계단 오르기 6-1 문제 해결 (0) | 2023.03.12 |