[dp/백준] 18353번: 병사 배치하기

-문제: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))