백준 14226번 이모티콘 JAVA

https://www.acmicpc.net/problem/14226

 

요구사항 정의

• 3개의 연산을 이용하여 S개의 이모지를 완성
  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
  3. 화면에 있는 이모티콘 중 하나를 삭제한다.
• 2 <= S <= 1000
• 각 연산은 1초씩 걸린다.

 

풀이 방법

숨바꼭질 문제와 비슷했다.

각 연산은 1초, 최소 시간으로 수행해야하므로 BFS로 풀어야겠다 라고 판단했다. 

 

이 문제에서 고민했던 점은 visited 배열의 차수, 배열의 크기이다.

 

2번 연산의 경우 화면의 개수뿐만 아니라 클립보드의 개수에 따라서 다음 개수가 변한다.

즉, 변수가 화면, 클립보드인 것이다. 따라서 2차원 배열로 방문여부를 표시하였다.

 

그리고 visited 배열의 크기는 요구사항에도 없었고 무엇을 기준으로 해야할지 모르겠어서

처음에는 S가 최대 1000이니 적당히 큰수인 10000으로 진행하였고 정답이었다.

 

풀이를 보니 S^2+1을 기준으로 하였는데

이유를 분석해보면 다음과 같았다.

 

1. 이모지를 1개씩만 계속 추가하면 최대로 걸릴 수 있는 시간은 S이다.
2. 하지만 S^2을 초과하고 3번 연산(화면-1)을 이용하여 S로 돌아갈 때는 걸리는 시간이 S를 넘게된다.
3. 따라서 S^2+1을 크기로 잡는 것