인프런 커뮤니티 질문&답변

저도 레고님과 같은 고민이 있었는데,

핵심은 '다이얼 돌리는 방법의 순서가 상관이 없다' 라는 것입니다.

(이유: 자물쇠 돌리기 한 번 한 것은 “인접한 1, 2, 3개의 디스크에 대해 ±1, ±2, ±3 만큼 숫자를 더하는 연산”으로 볼 수 있습니다. 이 연산들은 모두 각 디스크 위치에 더해지는 값들의 합을 계산하는 것이기 때문에, 덧셈이 교환법칙을 따릅니다. 즉, 같은 연산(같은 디스크 그룹에 같은 만큼 더하는 동작)을 순서를 바꿔 실행하더라도 최종 상태는 달라지지 않습니다.)

따라서, 레고님이 고민하시는

'만일 최적의 횟수가 맨 위가 아니라, 중간이나 맨 하단에서 다이얼을 돌리는 방법에서 비롯된 거면 어떡하지'

라는 부분에 대해서 설명드리자면,

초기 상태에서 최종 정답 상태에 도달하기 위한 연산이 A, B, C라고 하고 B, C가 중간이나 맨 뒤의 다이얼을 돌리는 연산이라고 했을 때, 정답 로직이 B -> C -> A라면 결국 이것은 똑같이 A -> B -> C로 치환이 가능합니다.

결과적으로, 앞에서부터 차례대로 최소 횟수를 찾아도 문제가 없습니다.

(ps. 이전 문제집에 있던 '동전 뒤집기' 또한 이런 방식으로 접근 가능합니다! 다시 풀어보시면 도움이 되실거에요)

안녕하세요 레고님 ㅎㅎ

그렇게 최적의 경우의 수를 생각하는 것자체는 너무 좋습니다. ㅎㅎ

다만 순서를 좀 조정하는게 좋을 것 같아요. 무식하게 모든 경우의 수 -> 그 다음 그게 안된다면 -> 최적 이렇게 순서만 정하면 더 좋아질 것 같습니다.

사실 그리고 다음의 생각을 볼까요?

'만일 최적의 횟수가 맨 위가 아니라, 중간이나 맨 하단에서 다이얼을 돌리는 방법에서 비롯된 거면 어떡하지'.

-> 맨하단에서 다이얼을 돌리는 것은 있을 수 없습니다.

문제 지문을 보시면... 다음과 같습니다

현재 자물쇠의 상태와 세준이의 비밀번호가 주어질 때, 자물쇠를 최소 몇 번 돌려야 풀 수 있는지 구하는 프로그램을 작성하시오.

즉, 현재 자물쇠의 상태로부터 -> 돌리기 때문에 갑자기 자물쇠의 끝 0부터 돌린다거나 9부터 돌린다거나는 있을 수 없습니다.

'현재 위치 N에서 다이얼을 맞추지 않고, 그 다음의 위치에 있는 다이얼을 먼저 맞춘 후, 다시 위치 N으로 돌아와서 다이얼을 맞추는 게 최적일 수도 있지 않을까.'

-> 이부분은 간단한 예시를 통해 반례를 찾아야 합니다. 이런 생각이 들지만 -> 어? 반례는 없을까? 하고 생각하는 로직이 습관화 되어야 합니다.

예를 들어

aaa -> bbb 로 가야 한다고 해볼게요.

aaa -> abb -> bbb 로 가는 것보다.

aaa -> bbb로 가는게 자명합니다.

즉, 현재위취에서 다이얼을 맞추는게 최적임을 간단한 예시로 어느정도 증명한 것을 볼 수 있습니다. (실제 증명은 이것보다 복잡하지만 간단하게 이렇게 반례 들면서 어느정도 타당한지를 가늠해봐야합니다.)

순서, 그리고 반례생각만 더 하시면 좋아지실겁니다. ㅎㅎ

감사합니다.