이진수 게임
면접 대비시간 제한1초메모리 제한1024 MB
두 이진 문자열이 주어질 때, 맨 앞 자리는 뒤집을 수 없는 단일 비트 뒤집기와 1 더하기, 1 빼기 연산만으로 시작 수를 목표 수로 바꾸는 최소 연산 횟수를 구한다.
문제
이진수 게임은 주어진 ‘시작 이진수’를 몇 가지 동작으로 ‘목표 이진수’로 바꾸는 게임이다.
이 게임에서 가능한 동작들은 다음과 같다.
- 한 자리 숫자를 보수로 바꾸기. 단, 맨 앞 숫자(Most Significant Digit)는 바꿀 수 없다.
101₂ → 111₂ - 현재 수에 1 더하기.
11₂ → 100₂ - 현재 수에서 1 빼기. 단, 현재 수가 0이라면 빼기가 불가능하다.
110₂ → 101₂
‘시작 이진수’와 ‘목표 이진수’가 주어질 때, ‘시작 이진수’를 ‘목표 이진수’로 만들기 위한 최소 동작 횟수를 출력하라. 주어지는 이진수들의 맨 앞 숫자는 항상 1이다.
입력
첫 번째 줄에 길이 L의 ‘시작 이진수’가 주어진다. 두 번째 줄에 길이 K의 ‘목표 이진수’가 주어진다. (1 ≤ L, K ≤ 10)
출력
‘시작 이진수’를 ‘목표 이진수’로 만들기 위한 최소 동작 횟수를 출력한다.