문자를 하나만 바꾸거나, 처음부터 연속된 k개를 바꿔서 전부 같은 문자로 바꾸는 다이나믹 프로그래밍

2806번: DNA 발견 A나 B로 이루어진 문자열에서 첫번째 연산은 하나의 문자를 A는 B로, B는 A로 바꾸는 것이다. 두번째 연산은 처음부터 연속된 K(1  예를 들어 ABBA라면, B 2개를 각각 A로 바꾸면 AAAA가 되고 처음부터 3개의 문자 ABB를 뒤집어서 BAA로 바꾸고, BAAA에서 첫번째 문자 B를 A로 바꾸면 2회만에 AAAA로 된다. 이러한 두 연산으로 모든 문자를 A로 바꾸고 싶다 가능한 최소 연산 횟수는? ----------------------------------------------------------------------------------------------------------------------------------------------------------..

• format_list_bulleted 다이나믹 프로그래밍
• · 2025. 2. 23.
• textsms

페리 수열(Farey sequence) 문제를 해결하기 위해 알아야 할 기본 성질 간단하게

1. n번째 페리 수열 0부터 1사이의 분모가 n이하인 모든 기약분수를 오름차순으로 나열한 수열 n = 1부터 8까지의 경우를 나열하면 다음과 같다. 2. 두 분수 사이에 있는 분수 theorem1) 0과 1 사이의 두 분수 $\frac{a}{b}$와 $\frac{c}{d}$에 대하여 $\frac{a}{b} 0$이다. 그런데 $$\frac{a+c}..

• format_list_bulleted 정수론
• · 2024. 2. 7.
• textsms