kkw564   4년 전

이걸로는 왜 해결이 안되는거죠??

같은 맥락으로 가장 긴 증가하는 부분 수열의 수를 찾고 n - 결과를하는것인데

왜 틀린걸까요..?

portableangel   4년 전

2,3,5가 순서대로 서있을 때, 4번이 2,3,5를 건드리지 않고 안에 들어갈 방법이 있을까요?
맨 앞이나 뒤로만 보낼 수 있다는 조건을 잘 생각해보시면, 옮겨지지 않은 아이들의 번호는 증가할 뿐 아니라 연속해야 한다는 사실을 알 수가 있습니다.

kkw564   4년 전

3

2 3 5를 입력시 제 코드는 답이 0이 나옵니다. 이문제의 핵심이 가장 긴 부분 증가 수열이어야 하는것으로 알고있습니다

portableangel   4년 전

예를 들어, 1 2 3 5 6 4 와 같은 배치에서, 한 명의 학생을 움직이는 것으로는 증가순으로 배치할 방법이 없습니다.

4번 학생이 가운데로 들어갈 수 없기 때문입니다. 답은 2명입니다. (5,6이 뒤로 옮겨짐)

실제로 학생을 옮겨 보시면 맨 앞/ 맨 뒤로 보내는 연산 2회 미만으로는 1 2 3 4 5 6을 만들 수 없다는 것을 보실 수가 있습니다.

말씀하신 LIS 풀이는 학생이 임의의 위치로 끼어들어갈 수 있는 문제에서의 풀이입니다.

움직인 학생을 최소화 = 움직이지 않은 학생을 최대화 -> 움직이지 않은 학생들은 증가 순이어야 함

으로부터 나온 풀이이고, 이 문제와는 다릅니다.

이 문제에도 똑같이 적용해보면,

움직인 학생을 최소화 = 움직이지 않은 학생을 최대화 -> 움직이지 않은 학생들은 증가 순이어야 하며, 번호가 서로 붙어있어야 함

으로 진행이 가능합니다.

kkw564   4년 전

감사합니다 이해하는데 도움이 됐네요 ㅎ

댓글을 작성하려면 로그인해야 합니다.