650. 2 Keys Keyboard

650. 2 Keys Keyboard

https://leetcode.com/problems/2-keys-keyboard/

문제

풀이(DFS)

DFS 탐색 그래프를 그리면 다음과 같다.

처음에는 무조건 Copy만 가능하므로 Copy부터 시작한다. 또한 Copy한 후에는 무조건 Paste를 해야 한다. Copy한 후 또 Copy를 할 수 없다.
반면에 Paste한 후에는 Copy할 수도 Paste를 할 수도 있다. 뼈대는 이렇게 구성하고 코드를 작성하였다.

함수 dfs 인자값을 설명하자면
cnt => 현재 복사된 문자 수
isCopy => 복사여부
step => 현재 step
total => 총 작성된 문자 수이다.
total이 n이면 구하고자 하는 step을 리턴해주고 그 이후라면 inf값을 리턴해주어 min값을 구할 때 날라가도록 하였다.
step == 0일 때 즉 처음에는 무조건 Copy만 할 수 있으므로 Copy = True로 바꿔주고 그 이외에는 Copy일 때에는 Paste만, Paste일 때에는 Copy, Paste를 나누어 탐색한다.

중요한 것은 Copy할 때 문제에서 Copy All이라고 명시하였으므로 cnt는 전체값 total이 된다.

결과(DFS)