박트리

그릇 모으기

문제

n개의 그릇 더미가 있다 각 그릇 더미는 최대 h개의 그릇이 쌓여있고 항상 큰 그릇 위에 작은 그릇을 놓을 때 주어진 연산들을 사용하여 한 개의 그릇 더미로 만드는 최소 연산 횟수를 구하는 문제이다.

문제 풀이

문제를 좀 더 단순화하여 약한 조건으로 생각해보자.

0번 그릇 더미를 새로 만들고 여기에 우리가 최후의 더미를 만든다는 조건과,

모든 그릇의 크기는 각각 다르다는 조건을 추가해보면 우리는 주어진 접시들을 소팅한 후 가장 큰 접시부터 0번 그릇 더미위에 올리면 된다.

따라서 현재 크기의 접시를 0번 그릇 더미 위에 올리는데 드는 연산 횟수는 다음과 같다.

먼저 현재 크기의 접시를 해당 그릇 더미 맨 아래 (그보다 큰 접시는 이미 0번 그릇 더미로 옮겨 졌기 때문에) 에서 분리하기 위해서는

현재 크기의 접시가 그릇 더미의 맨 꼭대기(현재 그릇 더미의 크기가 1) 이라면 0 아니라면 1의 연산으로 분리 가능하다. 

그리고 지금 0번 그릇 더미 맨 위에 올라와 있는 그릇의 더미 번호와 현재 접시의 더미 번호가 같다면 합치는데 비용이 -1이고 아니라면 1이다.

위와 같은 방식으로 구한 연산 횟수에 0번 그릇 더미(존재 하지 않는 그릇 더미)로 옮기는 연산 횟수인 1을 빼주면

우리가 구하고자 하는 최소 연산 횟수를 구할 수 있다. (시뮬레이션)

이제 문제는 같은 크기의 접시들이 여러개 존재 할 수 있다는 것인데, 

먼저 같은 그릇 더미에 같은 크기의 접시가 있다면 무조건(무적권!) 같이 움직이는게 이득이라는 점은 쉽게 생각할 수 있고,

다른 그릇 더미에서 같은 크기의 접시가 있을 때 어떤 순서로 0번 그릇 더미에 올려 놓을 것인가?

이 부분을 동적 계획법으로 구할 수 있다.

현재 크기의 접시를 모두 구해서 어떤 접시를 맨 아래로(현재까지 0번 그릇의 맨 위 접시와 관련이 됨) 보내고

어떤 접시를 맨 위로(다음에 들어오는 접시와 관련이 됨) 보낼지만 결정하면 가운데에 있는 접시들은 상관이 없다는 걸 알 수 있다.

따라서 

1. 현재 크기의 접시들중에 현재 0번 그릇 더미의 맨 위 접시의 더미 번호와 같은 접시가 있다면 

해당 그릇을 맨 아래로, 나머지 그릇들 중에 하나를 맨위로 보내고 연산수를 적절하게 구한다.

2. 존재하지 않는다면 맨 아래가 어떤 접시가 되도 상관이 없기 때문에, 하나의 그릇을 맨 위로 보내고 연산수를 적절하게 구하면 된다.

dp[i][j] = 0번 그릇 더미의 맨 위 그릇의 더미 번호가 j이고, 현재 i번째 크기의 그릇을 넣었을 때 최소 연산 횟수

로 정의 되고 현재 i 번째 그릇과 같은 크기를 가지는 그릇의 개수가 cnt개 라면

dp[ i+cnt ][ i 번째 그릇의 더미 번호 중 하나 ] = dp[i][j] + 연산수  로 구할 수 있다.

\(O(N^2H)\) 로 해결가능 하다.

소스 코드

코드 보기