프로그램 명: stfd_alignment
제한시간: 1 초
사과와 바나나는 맛있지만 위험하기도 합니다. 고대 예언자들은 사과와 바나나를 특정한 순서로 나열했을 때 이 세계가 멸망할 거라고 했습니다. 어느 구름낀 날, 살아가는 데 지친 당신은 이것이 사실인지 확인해보기로 했습니다. 사과와 바나나를 적절히 나열해두고 시작하는데 이 나열을 바꾸는 방법은 단 한가지입니다. 연속된 과일을 고르고 그 모든 과일을 사과나 바나나로 바꿀 수 있습니다. 하루 빨리 세상이 멸망하는 걸 보고 싶은 당신은 최소 몇 번 과일의 종류를 바꿔야 세상이 멸망하는지 알고 싶어합니다.
입력
-
첫 줄은 처음 나열
-
둘째 줄은 세상을 멸망시키는 나열
두 줄 모두 A 혹은 B로만 이루어진 문자열이며 A는 사과, B는 바나나입니다.
두 줄의 길이는 같으며 200자를 넘지 않고 공백을 포함하지 않습니다.
출력
세상을 멸망시키기 위한 최소 변경 횟수를 출력
두 번째 예제에서는 모든 과일을 사과로 바꾸고, 2번부터 3번까지를 바나나로 바꿔 2번만에 가능합니다
Apples and bananas are tasty, but also dangerous. An ancient prophecy said that when you align them in a certain order, the world will be destroyed! On a cloudy day, being tired of this world, you decide to try it out. You started with a line of apples and bananas, and there is one type of allowed operation: At each step, any number of consecutive items in the line can be chosen, replaced by the same amount of fruits of one kind. You can’t wait to destroy the world, so you want to know the minimum number of steps to achieve your goal.
입력
- The first line indicates the initial pattern,
- the second line indicates the evil pattern that can destroy the world. Both lines contain only characters ‘A’ and ‘
B’, where ‘A’ stands for an apple and ‘B’ stands for a banana. The two lines will have the same length (no great
er than 200), and there is no leading or trailing white spaces.
출력
Output a single line containing the minimum number of steps to destroy the world.
입출력 예
입력
BB
AA
출력
1
입력
BAAAB
ABBAA
출력
2
In the second case of this example, you can first transform the entire row of fruits into apples, and then turn the second through third fruits into bananas, which takes 2 steps total.
출처:standford/2008/
번역:ladown21
[질/답]
[제출 현황]
[푼 후(0)]