글 읽기 - 문제랑은 조금 다른 질문이요!! (응용!)

이 문제를 풀 때, LIS 알고리즘 사용해서 순서가 가장 긴 증가수열의 길이를 찾은 다음에,

전체 학생 수 - 가장 긴 증가수열의 길이 = 답

이런식의 알고리즘을 짜서 풀었습니다.

근데 만약, 1 2 3 4 5 6 7 이런 오름차순이 아니라

1. 3 5 9 7 1 이런식으로 주어진 순서에 맞게 학생들을 배치하는 할 수 있는 최소 경우의 수 라면 어떻게 구해야 할까요??

2. 또 주어진 순서는 3 5 9 7 1 이지만, 현재 있는 학생들이 1 3 9 번 학생만 있다하면 7과 5를 추가해야하잖아요? 이 땐 또 어떻게 해야할까요??

3,5,9,7,1 에 각각 순서를 부여 하는 규칙을 만들면 될 것 같습니다.

int map[N];

map[3] = 0;

map[5] = 1;

map[9] = 2;

이런 식으로요.

pinch3773님, 먼저 감사드립니다. 근데 어떤 말씀인지 잘 모르겠습니다..ㅠㅠ 죄송하지만, 자세히 말씀해주실 수 있나요??

3 5 9 7 1 가 각각 1 2 3 4 5 에 대응된다고 생각하시면 된다는 뜻인것 같습니다.

2번은 1 3 9 학생들로만 LIS를 찾고, 빠진 학생수만큼 더하면 되겠네요. (빠진 학생은 어디든 정답인 곳에 추가할 수 있을테니 말이죠!)

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

Baekjoon Online Judge