시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 95 28 26 37.143%

문제

이진수 게임은 주어진 ‘시작 이진수’를 몇 가지 동작으로 ‘목표 이진수’로 바꾸는 게임이다.

이 게임에서 가능한 동작들은 다음과 같다.

  1. 한 자리 숫자를 보수로 바꾸기. 단, 맨 앞 숫자(Most Significant Digit)는 바꿀 수 없다.
    1012 → 1112
  2. 현재 수에 1 더하기.
    112 → 1002
  3. 현재 수에서 1 빼기. 단, 현재 수가 0이라면 빼기가 불가능하다.
    1102 → 1012

‘시작 이진수’와 ‘목표 이진수’가 주어질 때, ‘시작 이진수’를 ‘목표 이진수’로 만들기 위한 최소 동작 횟수를 출력하라. 주어지는 이진수들의 맨 앞 숫자는 항상 1이다.

입력

첫 번째 줄에 길이 L의 ‘시작 이진수’가 주어진다. 두 번째 줄에 길이 K의 ‘목표 이진수’가 주어진다. (1 ≤ L, K ≤ 10)

출력

‘시작 이진수’를 ‘목표 이진수’로 만들기 위한 최소 동작 횟수를 출력한다.

예제 입력 1

110
1000

예제 출력 1

2

예제 입력 2

101
111

예제 출력 2

1