으잉? 저게 Accepted 받는다고여?

전 BFS 로 풀었는데...

이렇게 간단한진 전혀 몰랐네요 신기

@sonjaewon

저도 bfs로 풀고 저 코드를 봤습니다. 재귀로 구현해서 정말 예쁘게 구현이 되는 것 같네요

여담으로 이 문제에서는 n이 작아서 별 차이가 나지 않지만, n이 커진다면 저 방법보다 bfs가 평균실행시간이 짧지 않을까 싶네요 ㅋㅋㅋ

Q1.

우선 +1, -1, *2 연산을 통해 N에서 K로 가는 것과, -1, +1, /2 연산을 통해 K에서 N으로 가는 것은 동일한 문제입니다.

하지만 N->K는 {n-k}, {f(n+1, k), f(n-1, k), f(n*2, k)}로 케이스가 잘 나눠지지 않는데 비해 K->N은 {n-k}, {f(n, k-1), f(n, k+1)}, {k-n, f(n, k/2)}로 케이스가 잘 나눠져 비교적 재귀호출이 적습니다.

N>=K일 때는 K-N 이외에 다른 연산을 할 수 없기 때문에 K-N을 반환합니다.

N<K일 때,
K==1이면 N=0, K=1인데, Edge case로 처리해줍니다.
K가 홀수면 +1, -1 연산을 할 수 있습니다. 따라서 1+min(f(N, K-1), f(N, K+1))을 반환합니다.
K가 짝수면 /2 연산을 하거나 -1 연산을 K-N번 해서 바로 N으로 갈 수 있습니다.(최적의 해인 최소 연산 횟수를 구하는 것이기 때문에 +1 연산을 하는 경우 최적의 해가 아니게 됩니다(동전 dp문제에서 동전 가격이 1, 2, 4, 8과 같이 배수일 때와 비슷하게 그리디를 적용할 수 있습니다.))


따라서 K에 대해 모든 경우의 수를 포함하기 때문에 위와 같이 재귀함수를 구현할 수 있습니다.
+1, -1, *3의 경우 k%3!=0일 때 위/아래 3의 배수, 그 사이 K가 아닌 다른 수 모두를 포함해야 합니다. 따라서 아래와 같이 구현할 수 있습니다.

Q2.
그나마 종만북에서 보았던 것 중에 거꾸로 생각하기의 좋은 예시인 것 같습니다.

잘못된 내용 있으면 지적 부탁드립니다!