ian981130s   5년 전

나정돈은 장난감 가게에서 일하고 있다. 오늘은 가게 안에 있는 인형 코너의 정리를 하게 되었다.

인형 코너 선반에는 N개의 인형이 왼쪽에서 오른쪽으로 한 줄로 진열되어 있다. 선반은 N개의 칸으로 구분되어 있으며, 1개의 칸에는 1개의 인형을 놓는다. 

이 장난감 가게는 총 M종류의 인형을 팔고 있으며, 각각 1부터 M까지 번호가 매겨져 있다. 선반에 진열된 N개의 인형은 M종류 중 하나이다. 

또한 각 종류의 인형은 적어도 1개는 존재한다.나정돈은 보기 좋게 하기 위해 같은 종류의 인형이 모두 연속으로 놓이도록 정렬하고 싶어서 다음과 같은 방법으로 인형을 정렬하려고 한다.

    1. N개의 인형 중 일부를 선택하고 선반에서 꺼낸다. 안 꺼낸 인형의 위치는 움직이지 않는다.

    2. 꺼낸 인형을 같은 종류의 인형이 연속해서 놓일 수 있게 선반의 빈 구획에 넣는다.정렬한 후, 같은 종류의 인형이 모두 연속해서 놓여 있어야 한다. 정렬          하기 위해서 꺼낸 인형의 개수가 최소가 되도록 정렬할 때 최소값을 구하는 프로그램을 작성하라.


입력 설명

첫 번째 줄에는 2개의 정수 N, M이 공백으로 구분되어 입력된다. N은 인형의 개수이고, M은 종류 개수 이다. (1≤N≤100,000) (1≤M≤10)두 번째 줄부터 N줄에 걸쳐서 1이상 M이하의 정수가 한 개씩 입력된다. N행 중 i행 째(1≤i≤N)에 적힌 정수는 선반 왼쪽에서 i번째 칸에 놓인 인형의 종류를 나타낸다. 각 종류마다 적어도 1개의 인형은 존재하고 있음을 보장한다.


출력 설명

정렬하기 위해서 꺼낸 인형의 최소 개수를 출력한다.




위 문제를 푸는데 먼저 M종류 별로 순서를 정한 뒤, 이 순서와 각 종류별 개수를 통해 정답이 될 수 있는 배열들을 만들고, 이를 원래 배열과 비교하여 다른것이 바꿔야 되는 개수가 된다. 따라서 이 바꿔야할 개수들 중 최소값이 정답이다.


이 알고리즘으로 하는데 시간초과(1초)가 나옵니다. 혹시 위 문제를 부루트포스가 아닌 어떤방법으로 접근해야 할까요..??

meenook1109   5년 전

알고리즘 시간복잡도가 (M!*N)이라서 10!*100000 이라 시간초과가 난것 같네요. dfs로만 하는 것보다 정보를 배열에 저장해서 접근하는 dp방식을 도입하면 해결될 것 같네요.

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