1. 문제 링크 https://www.acmicpc.net/problem/2306 2306번: 유전자 DNA 서열은 4개의 문자 {a,c,g,t} 로 이루어진 문자열이다. DNA 서열에는 생명의 신비를 풀 수 있는 많은 정보가 들어 있다. 특히 KOI 유전자의 길이는 사람의 키와 깊은 상관 관계가 있다는 것이 알려� www.acmicpc.net 2. 문제 개요 DNA 서열은 4개의 문자로 이루어진 문자열이다. (1) at와 gc는 가장 짧은 길이의 KOI 유전자이다. (2) 어떤 X가 KOI유전자라면, aXt, gXc도 KOI 유전자이다. (3) 어떤 X, Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자이다. 문제에서 주어진 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI유전자..
1. 문제 링크 https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소� www.acmicpc.net 2. 문제 개요 초라기는 각각 W명으로 구성된 특수 소대를 다수 출동시켜 모든 구역에 침투시킬 예정이다. 특수 소대를 배치하는 데는 여러 조건이 있다. 원타곤의 모든 구역을 커버하기 위해 침투시켜야 할 특수 소대의 최소 개수를 출력하는 프로그램을 만들자. 3. 문제 힌트 문제를 곰곰히 생각해보면 타일링 문제와 상당히 비슷함을 알 수 있..
1. 문제 링크 https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마�� www.acmicpc.net 2. 문제 설명 DDR 게임을 하면서 발을 움직일 건데 가장 적은 에너지를 사용하여 움직일 때, 에너지의 최솟값을 찾자. 움직일 때 에너지 값은, 열에서 행으로 이동한다고 가정했을 때, 열 -> 행 0 1 2 3 4 0 1 2 2 2 2 1 0 1 3 4 3 2 0 3 1 3 4 3 0 4 3 1 3 4 0 3 4 3 1 이다. 3. 문제 힌트..
1. 문제 링크 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 개요 주어진 색상환의 인접한 색을 고르지 않는 것처럼 인접한 두 색을 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하자. 3. 문제 힌트 dp문제이다. dp를 [n][k]로 설계하고, n은 현재 고를 수 있는 색의 수, k는 이때까지 고른 색의 수로 정의하자. 4. 문제 풀기 인접한색을 선택하는 경우는 dp를 계산하면서 배제하기 때문에, 3차 배열..
1. 문제 링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하�� www.acmicpc.net 2. 문제 개요 어떤 문자열을 팰린드롬으로 분할하려고 한다. 분할의 개수의 최솟값을 구하시오, 즉 원소의 개수가 최소가 되도록 해야 함. 3. 문제 힌트 처음에 분할의 최솟값이라고 하길래 분할하면 분할했지 분할의 최솟값은 뭐지?라고 생각했다. 질문란 이런 곳을 찾아보니 분할의 경우의 수가 아니고 분할했을 때 원..
1. 문제 링크 https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 2. 문제 설명 대회가 끝나고 난 후에 각자 선물을 전달하려고 할 때, 선물을 나누는 경우의 수를 구하는 프로그램을 작성하시오. 모든 사람은 선물은 하나씩 받으며, 자기의 선물을 자기가 받는 경우는 없다. 3. 문제 힌트 기존의 그룹(n - 1명)에 최적화된 답을 알고 있다고 가정하자. n - 1명이 있는데, 새로운 사람x가 들어온다. ( 이제 n명이 됨. dp[n]을 구할 것. ) (1) x가 1번사람이 받은 선물과 바꾼다. (1번 사람의 선물이 아닌, 1번 사람이 받은 선물이다.) (2) x가..