백준/DP
[dp/백준] 18353번: 병사 배치하기
ydin
2022. 5. 27. 13:38
-문제:https://www.acmicpc.net/problem/18353
이는 주어진 정보를 역순으로 한 뒤에
증가하는 가장 긴 수열의 길이를 구해
전체 길이에서 빼면 답이 나온다
처음에는 for문 두개가 아니라 한개로 했는데, 이때 틀렸다.
이유는 0부터 i번째까지 증가하는 수열을 찾아야하는데, for문이 하나면, 국소적으로 i랑 i-1번째랑만 비교하므로 전체적인 수열을 구할 수 없다.
for문 두개를 이용하면 답이 나온다.
여기에서 length[i]+=1의 위치가 for j~를 나올 때 수행돼야 정답이 나오는지 궁금했다.
그래서 두가지 경우에 대해 결과를 도출해봤다
1.
for i in range(n):
for j in range(i):
if data[i]>data[j] and length[i]<length[j]: #큰 수가 수열에 포함되지 않는 경우
length[i]=length[j] #이전 수열 값 누적
length[i]+=1
이 경우에는 length의 모든 원소가 0인데, 크기 차이가 있어야지 +1 연산이 가능하기때문에
결국 length의 모든 원소가 0인 상태로 끝난다 (length=[0,0,0,0,0,0,0])
2.
for i in range(n):
for j in range(i):
if data[i]>data[j]: #큰 수가
if length[i] <length[j]: #수열에 포함되지 않을 경우
length[i]=length[j] #이전 수열 값 누적
length[i]+=1
이 경우는 data[i]> data[j]이 아닌 경우에도 length[i]+=1 연산이 수행된다.
length = [0,1,2,3,4,5,6]
정답은 인덱스 5의 값이 2여야 하고, 인덱스 6은 4, 인덱스 7은 5여야 한다
-정답풀이:
n=int(input())
array=list(map(int,input().split()))
length=[0]*n
data=[0]*n
for i in range(n):
data[i]=array[n-1-i]
for i in range(n):
for j in range(i):
if data[i]>data[j]: #큰 수가
if length[i] <length[j]: #수열에 포함되지 않을 경우
length[i]=length[j] #이전 수열 값 누적
length[i]+=1
print(n-max(length))
-틀린 풀이
n=int(input())
array=list(map(int,input().split()))
length=[0]*n
data=[0]*n
for i in range(n):
data[i]=array[n-1-i]
for i in range(1,n):
if data[i]>data[i-1]:
if length[i]<length[i-1]:
length[i]=length[i-1]+1
print(n-max(length))