synoti21   2년 전

preview


문제 - 용액 붓기

철수는 10가지의 시험관을 가지고 있고, 시험관에는 총 여덟 가지의 용액이 층을 이루어 담겨져 있다. 용액들은 서로 섞이지 않으며 반드시 층을 이루고 있다.

[0,1,2,3,3,5]은 시험 관의 맨 위는 비어져 있고, 순서대로 1번 용액, 2번 용액, 3번 용액이 두 층, 5번 용액이 쌓여 있는 것을 의미한다. 그림의 첫 번째 시험관과 같은 모양이다. 즉, 배열의 맨 앞이 시험관의 맨 위, 그리고 배열의 맨 뒤가 시험관의 맨 밑을 의미하는 것이다. 또한, 0은 용액이 그 층에 없다는 뜻이다.

규칙:

  1. 용액과 용액 사이에는 빈 공간이 없다. 즉, [0,0,3,0,2,2]는 불가능한 상태이다. 3번 용액과 2번 용액 사이에 빈 공간이 있기 때문이다. 단, [0,0,3,1,2,2]는 가능하다.

  2. 한 시험관에서 다른 시험관으로 용액을 부을 때는 반드시 다른 종류의 용액이 나오기 직전까지 부어야 한다. [1,1,2,3,4,1] 일 경우, 1번 용액이 맨 위에 두 겹 쌓여있으므로 용액을 부은 후의 상태는 [0,0,2,3,4,1] 이 되어야 한다. 즉, 그 밑의 층인 2번 용액부터는 부어서는 안된다.

  3. 한 시험관에서 다른 시험관으로 용액을 부을 때, 맨 위에 서로 같은 종류의 용액이 있어야 부을 수 있다. 즉, [0,0,1,2,4,1] 에서 [0,0,1,4,3,3] 으로 부을 수 있지만, [0,0,1,2,4,1] 에서 [0,0,3,4,1,2]로 부을 수 없다.

  4. 시험관의 용량은 총 6이며, 옮겨 부을 때 넘쳐서는 안된다. 즉, [0,0,1,1,2,3] 에서 [0,1,1,3,4,5] 로 부을 수 없다. 1번 용액이 두 겹 쌓여 넘쳐 흐르기 때문이다.

  5. 용액을 옮겨 붓고, 해당 시험관이 비어있는 상태면, 용액의 종류와 상관없이 부을 수 있다. 단, 위의 규칙을 준수하며 부어야 한다.

철수는 가장 적은 횟수로 용액을 옮기며 모든 시험관에 같은 종류의 용액만이 담기도록 하려 한다.

즉, [0,0,1,4,3,2], [0,0,1,2,2,3], [0,0,4,2,3,1],[0,0,3,2,1,1] 을

[0,1,1,1,1,1], [0,0,3,3,3,3], [0,2,2,2,2,2], [0,0,0,0,4,4] 이런식으로 옮기는 것이다.

이 때, 모든 시험관에 같은 종류에 용액이 담기도록 하는 가장 적은 횟수를 구하는 알고리즘을 작성하시오. 어떠한 경우에도 옮길 수 없으면 -1을 반환한다.

더 어려운 버전

이 때, 가장 적은 횟수로 모든 시험관에 같은 종류에 용액이 담기도록 하는 순서를 배열의 형태로 반환하는 알고리즘을 작성하시오. 어떠한 경우에도 옮길 수 없으면 [-1]을 반환한다.

즉, 3번째 시험관에서 5번째 시험관으로 붓고, 4번째 시험관에서 3번째 시험관으로 붓는 경우, [[3,5],[4,3]] 형식으로 반환해야 한다.

친구랑 게임하다가 문득 생각나서 한번 만들어봤습니다 ㅋㅋㅋ 비슷한 문제 무조건 있을 것 같기는 한데 한번 공유해봅니다...

밑은 제 블로그에 올린 게시글입니다. (문제가 될 시 바로 삭제하겠습니다.)

https://velog.io/@synoti21/my-liquid-problem

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