728x90 반응형 19691 2022.02.14 [백준] (python 파이썬) DNA https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 풀이 처음 이 문제를 이해하기가 어려웠다. 그래서 구글링 중, 위 그림을 발견하였다. 위의 그림처럼 같은 위치에 있는 DNA중 가장 많이 나온 DNA와 그 DNA를 제외하고 나온 DNA의 갯수를 모두 더해주면 답을 구할 수 있다. 이 문제는 각 상황에서의 최선을 찾는 문제이기 때문에 그리디 알고리즘을 사용할 수 있다. 1 2 3 4 5 6 7 8 9 1.. 2022. 2. 14. 이전 1 다음 728x90 반응형