질문&답변
8-F 유형의 문제를 풀 때 어려운 점
저도 레고님과 같은 고민이 있었는데, 핵심은 '다이얼 돌리는 방법의 순서가 상관이 없다' 라는 것입니다. (이유: 자물쇠 돌리기 한 번 한 것은 “인접한 1, 2, 3개의 디스크에 대해 ±1, ±2, ±3 만큼 숫자를 더하는 연산”으로 볼 수 있습니다. 이 연산들은 모두 각 디스크 위치에 더해지는 값들의 합을 계산하는 것이기 때문에, 덧셈이 교환법칙 을 따릅니다. 즉, 같은 연산(같은 디스크 그룹에 같은 만큼 더하는 동작)을 순서를 바꿔 실행하더라도 최종 상태는 달라지지 않습니다.) 따라서, 레고님이 고민하시는 '만일 최적의 횟수가 맨 위가 아니라, 중간이나 맨 하단에서 다이얼을 돌리는 방법에서 비롯된 거면 어떡하지' 라는 부분에 대해서 설명드리자면, 초기 상태에서 최종 정답 상태에 도달하기 위한 연산이 A, B, C라고 하고 B, C가 중간이나 맨 뒤의 다이얼을 돌리는 연산이라고 했을 때, 정답 로직이 B -> C -> A라면 결국 이것은 똑같이 A -> B -> C로 치환이 가능합니다. 결과적으로, 앞에서부터 차례대로 최소 횟수를 찾아도 문제가 없습니다. (ps. 이전 문제집에 있던 '동전 뒤집기' 또한 이런 방식으로 접근 가능합니다! 다시 풀어보시면 도움이 되실거에요)
- 좋아요수
- 0
- 댓글수
- 2
- 조회수
- 84