접근
이런 되게 심플한 문제임. 그러면 일반적인 접근은 아래와 같음.
- 특정 수열이 팰린드롬인지 확인하는 함수 하나를 만든다.
- FOR문 돌리면서 S랑 E를 입력받아서 해당 S부터 E까지 수열이 팰린드롬인지 확인하고 결과를 출력한다.
실제로 이 방법이 틀린 방법은 아님. 그러나 본 문제에서 입력되는 값의 범위가 다음과 같음.
N이 2000임. N ^ 2이 4,000,000임. 그리고 M은 1,000,000임.
따라서 시간복잡도로 따지면 O (N ^ 2 / 4) ≒ O(M) 임. 근데 BIG O에서는 CONSTANT로 나누는 건 없애도 동일하다고 함 따라서 O(N ^ 2) == O (M) 임.
이걸 알고 위에 직관적으로 튀어나오는 풀이를 바라보면 느낌이 옴.
- FOR문 돌리면서 S랑 E를 입력받아서 해당 S부터 E까지 수열이 팰린드롬인지 확인하고 결과를 출력한다.
M번 FOR문을 돌리면서 최대 N만큼의 수열을 반복 확인후 결과를 만들어내는데, 이는 시간복잡도가 O( M * N) 이며 위에 O (M)은 O(N^2)이라고 봐도 된다고 했으니 실질적 시간복잡도는 O (N^3)임.
저 방식으로 구현후 돌리면 거의 무조건 시간초과가 뜬다.
DP로 풀어야한다.
DP. 솔직히 DP 문제를 선호하진 않는다. 처음 접근 힘든게, 어려운 수학문제를 처음 봤을때 느낌과 같아서 그렇다. 그러나 DP가 그만큼 효율적으로 풀어내는 문제도 많은 만큼 익숙해져야하며, 이 문제도 다른 풀이법도 있겠지만 DP를 통해서 풀어내야한다.
- DP인 만큼 이전 값을 저장할 곳이 필요하다.
- 알아야하는 입력같이 S~E이다.
- DP로 저장할 배열을 2차원 배열로 설정하는게 맞겠다 생각이 들었다.
2차원 배열로 설정하면 DP[S][E] 로 설정하게 될텐데, 의미는 S부터 E까지 수열이 팰린드롬이냐 아니냐이다. 팰린드롬이면 1, 아니면 0을 입력한다.
초기 방식
가장 처음에 언급했던 팰린드롬 확인 함수를 구현후 이를 활용하여 구하는 방식이다.
for s in range(n):
for e in range(s,n):
# sol function is the function that check palindrome
result = sol(s,e)
# If num List from s to e is palindrome,
if result == True:
board[s][e] = 1
# Num List is not palindrome
else:
board[s][e] = 0
구조는 되게 간단하다 시작하는 s 전부다, e 전부다 일일이 구해서 s에서 e까지 수열이 펠린드롬인지 확인하는 방식이다. 알다시피 이중 for문이라 O(N ^ 2 ) 인데 팰린드롬 확인 함수 역시 O(N)이라서 저 부분에서 O(N^3)이 나온다.
고민
DP란 무엇인가. 점화식이다. 점화식은 무엇인가.
N = 1일때, 특정 값이 있고, N+1 일때는 N일때 값에 어떤 연산으로 N+1 값을 얻어내는 것이다.
이 점을 깨닫고 보니 N을 S와 E로 두는게 아니라 수열의 길이로 보아야하는걸로 보였다. 그러고보니 생각보다 잘 풀렸다.
구현 시작
l이 길이라고 하자.
-
l = 1 일때는? 길이가 1인 수열은 무조건 좌우 대칭이다. 팰린드롬이다.
-
l = 2 일때는? 왼쪽 숫자와 오른쪽 숫자가 같으면 팰린드롬이다.
-
그러면 l = 3이상일때는 어떻게 해야하는가?
바로 양끝 숫자 사이에 가운데 숫자가 팰린드롬이어야한다.
또한 양끝의 숫자가 같으면 된다.
길이를 1부터 시작해 N까지 늘려나가면 가운데 수열이 팰린드롬인지 확인하는건 논리적으로 가능하다. 왜냐하면 가운데 수열은 최소 길이가 1이어야하는데 길이가 1인 수열과 2인 수열은 우리가 초기값으로서 구할 수 있기 때문이다. 따라서 부분 수열의 길이 L을 기준으로 L이 1부터 N까지 늘려나가며 DP 값을 구하면 된다.
nList = list(map(int,input().split()))
#dp가 저장될 값.
board = [[ None for _ in range(2001)] for _ in range(2001)]
# 부분 수열의 길이 l
for l in range(1, n+1):
# 시작 지점인 s
for s in range(n - l + 1 ):
# e는 수열 마지막 지점 인덱스 값이다.
e = s + l -1
# l이 1이라면 숫자가 하나밖에 없으니 무조건 맞다.
if l == 1 :
board[s][e] = 1
# l가 2라면 첫번째 숫자와 두번째 숫자가 같으면 팰린드롬이다.
elif l == 2:
if nList[s] == nList[e]:
board[s][e] = 1
else:
board[s][e] = 0
# l이 3이상이라면 양끝을 제외한 가운데가 팰린드롬인지 확인. 이는 board값에 저장되어있음. 그리고 양 끝 값이 같은지 확인. 전부 맞다면 s부터 e까지 수열도 팰린드롬임.
else :# l >= 3
if board[s+1][e-1] == 1 and nList[s] == nList[e]:
board[s][e] = 1
else:
board[s][e] = 0 추가로 알아야할 점
입력받은 횟수가 많은 m이 1,000,000임. 백만임. 이는 절대 적은 숫자가 아님. 이만큼 입력을 받는 상황일 때 각종 프로그래밍 언어에서 빠르게 입력받을 수 있는 방법들이 있음. 그걸 활용해야함.
해당 방법을 테스트 해볼 수 있는 문제는 아래 링크와 같음.
필자는 파이썬으로 문제를 푼만큼 빠른 입력을 위해 다음과 같은 방법을 사용하였음.
import sys
input = sys.stdin.readline
보통 입력받기 위해 input() 함수를 많이 사용할텐데, 이는 의외로 느림. 그래서 빠른 sys.stdin.readline 함수를 사용함. 그런데 이 함수는 input과 다르게 문자열 입력받고 마지막에 개행문자도 같이 받음. int형 변환할때는 사라지지만 문자열 그자체를 다룰 땐 문제가 있음. 그래서 strip 함수를 통해 개행문자를 지워야함.
import sys
input = sys.stdin.readline
a = input().rstrip()
결과
