boj 9665 : GMO

boj 9665 : GMO

https://www.acmicpc.net/problem/9665

문제를 잘 못 이해해서 여러 번 틀렸고, 제대로 이해한 후에도 어렵게 생각하여 시간초과를 냈다...

사실은 쉬운 문제이다.

역시 알고리즘은 열린 사고를 강요한다. ㅎㅎㅎㅎ

 N*M 만에 풀리는 기초적으로 떠올릴 수 있는 알고리즘으로 해결할 수 있다.

돼지 유전자를 사과 유전자가 대체할 수 있으면 사과 유전자로 하고, 사과 유전자로 대체할 수 없으면 돼지 유전자를 이용한다.

이 방법으로 사과 유전자의 모든 위치에서 돼지 유전자를 주입할 때의 코스트를 구하고, 그 코스트들 중 최소값을 출력하면 정답.