1부터 N까지의 모든 자연수로 구성된 길이 N의 수열이 주어집니다.
이 수열의 왼쪽 맨 끝 숫자 또는 오른쪽 맨 끝 숫자 중 하나를 가져와 나열하여 가장 긴 증가수열을 만듭니다.
이때 수열에서 가져온 숫자(왼쪽 맨 끝 또는 오른쪽 맨 끝)는 그 수열에서 제거됩니다.
예를 들어 2 4 5 1 3 이 주어지면 만들 수 있는 가장 긴 증가수열의 길이는 4입니다.
맨 처음 왼쪽 끝에서 2를 가져오고, 그 다음 오른쪽 끝에서 3을 가져오고, 왼쪽 끝에서 4,
왼쪽 끝에서 5를 가져와 2 3 4 5 증가수열을 만들 수 있습니다.
▣ 입력설명
첫째 줄에 자연수 N(3<=N<=100)이 주어집니다.
두 번째 줄에 N개로 구성된 수열이 주어집니다.
▣ 출력설명
첫째 줄에 최대 증가수열의 길이를 출력합니다.
두 번째 줄에 가져간 순서대로 왼쪽 끝에서 가져갔으면 ‘L', 오른쪽 끝에서 가져갔으면 ’R'를 써
간 문자열을 출력합니다.(단 마지막에 남은 값은 왼쪽 끝으로 생각합니다.)
▣ 입력예제 1
5
2 4 5 1 3
▣ 출력예제 1
4
LRLL
▣ 입력예제 2
10
3 2 10 1 5 4 7 8 9 6
▣ 출력예제 2
3
LRR
선택권은 가장 왼쪽 수를 가져오거나 가장 오른쪽 수를 가져오는것이다.
그러면서 증가하는 조건을 만족해야한다.
이때 가장 길게 만들어야한다.
import sys
sys.stdin=open('input.txt','r')
if __name__=="__main__":
N=int(input())
arr=list(map(int, input().split()))
res=[]
ans=''
lt=0 # 가져올 왼쪽 index
rt=N-1 # 가져올 오른쪽 index
last=0 # 가장 마지막에 가져 온 수, 다음 수가 이것보다 커야지 가져올 수 있음
while lt<=rt:
# 순서 상관없이 2개씩 넣는 것을 시도한다. 가장 마지막 수보다 크기만 하면 넣는다
if arr[lt]>last: #
res.append((arr[lt],'L'))
if arr[rt]>last:
res.append((arr[rt],'R'))
if len(res)==0: # 위 코드를 수행하지 않았다. 더 이상 넣을 수 있는 게 없다
break # 종료
else:
res.sort() # 1개 또는 2개가 들어 갔다. 정렬함으로써 둘중 더 작은 값을 사용한다
ans=ans+res[0][1] # 둘중 작은 값에서 문자를 가져와 문자열을 붙인다
last=res[0][0] # 둘중 작은 값에서 수를 가져와 업데이트
if res[0][1]=='L':
lt+=1
else:
rt-=1
# 동시에 두개 넣고 하나 넣고 남은 하나를 이용안하고 버리는 이유는
# 다음 왼쪽 또는 오른쪽이 더 작은 수 일 수 있기 때문이다.
res.clear()
print(len(ans))
print(ans)
