문제 바로가기
문제:
명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.
- S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
- S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
- S = 3, E = 3인 경우 1은 팰린드롬이다.
- S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.
자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다. 둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다. 셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다. 넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.
출력:
총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.
풀이:
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input())
lst = list(map(int,sys.stdin.readline().split(" ")))
M = int(input())
res = []
for i in range(M):
left , right = map(int,sys.stdin.readline().split(" "))
temp = lst[left-1:right]
if "".join(str(temp)) == "".join(str(temp[::-1])):
res.append(1)
else:
res.append(0)
for i in res:
print(i)그냥 풀면 슬라이싱에서 엄청난메모리를 사용한다. 그리고 이 문제에서 시간초과가난다.
어떻게 풀어야할까 생각을 해보았다.
N= 2000 이다 dp를 2차원 배열로 만들면 되나 ?? 4000000 1억정도가 1초인데 400만이면 할 만 하다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n = int(input())
lst = list(map(int,sys.stdin.readline().split(" ")))
m = int(input())
dp = [[0] * (n) for _ in range(n)]
# 길이가 1 일때
for i in range(n):
for j in range(n):
if i == j :
dp[i][j] = 1
#길이가 2 일때
for i in range(n-1):
if lst[i] == lst[i+1]:
dp[i][i+1] = 1
# 길이가 3 이상일때.
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
# i는 시작지점 j는 끝지점 i와 j가 같고 [i+1][j-1] 이 팰린드롬이면 이것도 팰린드롬이다.
if lst[i] == lst[j] and dp[i+1][j-1]:
dp[i][j] = 1
res = []
for _ in range(m):
left , right = map(int,sys.stdin.readline().split(" "))
res.append(dp[left-1][right-1])
print(*res,sep="\n")
길이가 1일때는 i == j 일때 이다 다 1로 바꿔주고
길이가 2일때는 i+1 = i 일때 즉 22 처럼 연속된 숫자일 경우에만 같다.
길이가 3 이상일때부터 이제 문제다
i는 시작지점이고 j는 끝지점이다. length = 3 일때
i 값에따라 (0,2) , (0,3) 이렇게 차이가 난다
만약에 시작과 끝값이 같게되면 [시작+1][끝-1] 도 팰린드롬이면 양 옆에 똑같은 숫자를 더하게 되면
똑같이 팰린드롬이 되는 개념이다.
(Python/🥇4)백준알고리즘 9251번: LCS
문제바로가기 문제: LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 A
windy7271.tistory.com
(Python/🥈1)백준 알고리즘 1105번:가장 긴 증가하는 부분 수열
문제 바로가기 문제 : 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10
windy7271.tistory.com
팰린드롬수열, LCS, LIS 수열관련 응용 문제들이 많이 나올거 같다 잘 알아두어야겠다
댓글