[BOJ] 16197 - 두 동전

문제 출처

백준 16197 - 두 동전

 

풀이

문제의 핵심은 두 가지라고 생각했습니다.

 

1. 두 동전 중 하나만 보드에서 떨어뜨려야 한다.

2. 동전을 움직이는 버튼은 최대 10번까지만 누른다.

 

동전을 움직이는 버튼을 10번보다 많이 눌러야 한다면 더이상 버튼을 누르지 않기 때문에 동전이 움직이는 경우의 수의 최대가 다음과 같았습니다.

 

4¹ + 4² + . . . + 4¹⁰

 

따라서 경우를 모두 돌려도 시간초과가 나지 않을 것이라 예상했습니다.

 

동전을 위, 아래, 왼쪽, 오른쪽으로 움직여서 탐색하는 bfs를 사용했습니다.

 

문제에 나와있는 그대로 움직이는 것을 구현해서 모든 경우를 봐주어 최소 값을 구해주었습니다.

 

코드

small-j/BOJ_Algorithm