10942번: 팰린드롬?
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
www.acmicpc.net
입력
1.N(문자열 길이)
2. M(질문의 개수)
3. S, E(S번째부터 E번째 까지의 부분 수열 인덱스)
출력
1.입력된 S E 의 인덱스를 보고 수열 S->E 까지의 문자열이 팰린드롬이라면
1 출력,,, 아니면 0 출력
생각방법
DP문제다. 점화식을 고민하자
제 10 장 오토마타 , 문법 , 언어
제 10 장 오토마타 , 문법 , 언어. 오토마타 (Automata) 오토마타 이론과 컴퓨터 관련 학문 오토마타와 관련된 3 가지 개념 유한 오토마타 오토마타의 응용 문법 (grammar) 과 언어 (language) 튜링머신 (Turi
www.slideserve.com
여기서 중요한점은
1.DP[i][i] 은 모두 팰린드롬이다.
2.길이가 2인 | arr[i]와 arr[i+1] (단,i +1 <= N) |을 포함하는 부분문자열 이 같다면, 그것 또한 모두 팰린드롬 일것이다.
3.제일 중요한것! DP 만들기 길이가 3이상인 부분문자열 확인할것이다.
left 인덱스 "L" right 인덱스 "R" 가 있다고 하자 (단, 1 <= L < R <= N)
> arr[L] == arr[R] 이면서~(위의 펠린드롬 정의의 (2)을 참고할때 arr[L] , arr[R] 는 'a'가 될 부분이다.)
> DP[L+1][R-1] (위의 펠린드로 정의의 (3)을 참고할때 DP[L+1][R-1]는 'x'가 될 부분이다.)
DP[L+1][R-1] 이 펠린드롬이라면 DP[L][R] 또한 펠린드롬일것이다.
사용하는 자료구조
2차원 배열!
>DP 배열
1차원 배열
>arr 자료담기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <iostream>
using namespace std;
int dp[2020][2020];
int arr[2020];
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
//---------------------------
int N; cin >> N;
for (int i = 1; i <= N; i++)
cin >> arr[i];
//---------------------------
for (int i = 1; i <= N; i++)
{
dp[i][i] = 1;
if (i+1 <= N && arr[i] == arr[i + 1]) {
dp[i][i + 1] = 1;
dp[i+1][i] = 1;
}
}
for (int i = 1; i <= N; i++){
for (int j = 1; j <= N; j++){
int l = i, r= j;
if (i > r)
if (1 <= r-1 && l+1 <= N) {
if (arr[l] == arr[r] && dp[l + 1][r - 1] == 1) {
dp[l][r] = 1;
dp[r][l] = 1;
}
}
}
}
//---------------------------
int M; cin >> M;
for (int i = 1; i <= M; i++)
{ int S, E; cin >> S >> E;cout << dp[S][E] << '\n';}
//---------------------------
return 0;
}
|
cs |
'컴퓨터 > 알고리즘' 카테고리의 다른 글
[프로그래머스] string 입력 참고 (0) | 2021.06.28 |
---|---|
[백준 10828번] 스택 - 1차 스터디 A (0) | 2021.06.25 |
|정렬 알고리즘|버블, 선택, 삽입, 퀵, 병합, 힙 정렬 연습 (0) | 2021.02.10 |
|코린이의 코포| Round 698 Div.2 (A, B) 참고에 도움안되는 솔브 (0) | 2021.01.29 |
[백준 11060번] 점프 점프 |DP연습| (0) | 2021.01.19 |