18353번 - 병사 배치하기
안녕하세요. LIS 이용해서 가장 긴 감소하는 부분 수열 이용해서 풀긴 풀었는데
처음 생각한 방식이 왜틀렸는지 모르겠어요.
처음 생각한건 d배열을 모두 0으로 초기화 해줍니다.
arr을 순차적으로 검색해서
arr[i] < arr[i+1] 이면 내림차순이 안되니 d[i] = 1; 하면 d[i]를 제거해야된다는 체크가 되서
d[i] 가 1인 것만 체크해서 개수를 답으로 출력했는데
틀렸따고 나오네요. 저런식으로 해도 가능하지않나요?
3개 테스트돌려봤느데 잘나옵니당.
715 11 4 8 5 2 4출력 : 2
11000000출력 : 0
11
출력 : 0
나는 바보입니다.
댓글을 작성하려면 로그인해야 합니다.
jikimee64 3년 전
안녕하세요. LIS 이용해서 가장 긴 감소하는 부분 수열 이용해서 풀긴 풀었는데
처음 생각한 방식이 왜틀렸는지 모르겠어요.
처음 생각한건 d배열을 모두 0으로 초기화 해줍니다.
arr을 순차적으로 검색해서
arr[i] < arr[i+1] 이면 내림차순이 안되니 d[i] = 1; 하면 d[i]를 제거해야된다는 체크가 되서
d[i] 가 1인 것만 체크해서 개수를 답으로 출력했는데
틀렸따고 나오네요. 저런식으로 해도 가능하지않나요?
3개 테스트돌려봤느데 잘나옵니당.
7
15 11 4 8 5 2 4
출력 : 2
1
1000000
출력 : 0
1
1
출력 : 0