[백준 14226번] 이모티콘 - java

문제 설명

1. S가 주어진다. 1개의 이모티콘을 갖고 있다.

2. 1초마다 전체복사/붙여넣기/지우기 중 하나를 할 수 있다.

3. 1개의 이모티콘 -> S개의 이모티콘 을 만드는 최소의 연산을 구하면 된다.

풀이 과정

 1. BFS를 생각하고 풀었는데, BFS적용 자체는 간단하지만 시간복잡도에서 터지지 않게 하는 것이 복잡했다.

 2. BFS풀이법

   - Queue를 구현한다. Queue는 ( 현재이모티콘수, 복사한이모티콘수, 걸린시간 ) 세 개의 구성을 갖는 class를 갖는다.

   - 시작은 1, 0, 0이다. ( 처음이모티콘 1개, 복사x, 0초)

   - 1초마다 걸리는 연산은 복사하기, 붙여넣기, 지우기이다.

     - 복사하기 : Queue에 ( 현재이모티콘수, 현재이모티콘수, 걸린시간+1 ) 을 해주면 된다.

     - 붙여넣기 : Queue에 ( 현재이모티콘수+복사한이모티콘수, 복사한이모티콘수, 걸린시간+1 ) 을 해주면 된다.

     - 삭제하기 : Queue에 ( 현재이모티콘수-1, 복사한이모티콘수, 걸린시간+1 ) 을 해주면 된다.

 3. BFS는 Queue로 진행되기 때문에 걸린시간은 작은 숫자부터 하나씩 늘어날 것이다. 따라서 결과를 구하려면 Queue의 첫번째 인자->현재이모티콘수 를 하나씩 S와 비교하다가 둘이 일치하는 첫 번째 순간의 걸린시간이 answer이 될 것이다.

     따라서 처음으로 S = 현재이모티콘수 가 되는 순간 answer에 걸린시간을 저장하고 그 이상 진행할 필요가 없다.

 

 4. 여기까지는 간단히 구현이 가능하다. 진짜 난이도를 가르는 부분은 시간복잡도와 관련된 check이다.

 5. 보면 알겠지만 BFS의 Queue는 매번 3개씩 실행된다. 그런데 만약에 한번 방문한 곳을 나중에 다시 방문하게 되면 시간복잡도가 엄청나게 늘어날 것이다. 이미 방문했는데 그곳에서 또 똑같은게 3번 실행.....이렇게 진행되면 문제가 생긴다.

 6. 이를 반복하기 위해 동일한 경우를 체크해준다. 여기서 주의할 점은 똑같이 3개의 이모티콘을 갖고 있는 경우여도, 복사한 이모티콘이 다른 개수이면 BFS를 실행할 때 다른 경우로 분기한다는 것이다.

 7. 그렇기 때문에 check[현재이모티콘][복사한이모티콘] 으로 bool배열을 만들어 체크해주면 동일한 경우만 체크해 줄 수 있다.

 

 8. 그리고 생각해야 할 점은, 문제에서 이모티콘의 개수를 정의해 주었다는 것이다. 그에 맞춰 적절히 조건을 추가해 주면 된다.

 9. 예를 들어 복사의 경우 최대 이모티콘의 개수보다 두 배 이상 높아질 수는 없을 것이다.

               붙여넣기 경우 현재이모티콘의 수와 복사한 이모티콘의 수가 최대값을 넘지 않을 것이다.

                 빼기의 경우는 계산 이후 0보다는 큰 값이 나와야 할 것이다.

코드