[BOJ 2306] 유전자

https://www.acmicpc.net/problem/2306 - 문제 요약 DNA 서열은 4개의 문자 {a,c,g,t}로 이루어진 문자열이다.또한 KOI 유전자는 아래의 3가지 조건을 만족한다.at와 gc는 가장 짧은 길이의 KOI 유전자이다.어떤 X가 KOI 유전자라면 aXt와 gXc도 KOI 유전자이다.어떤 X와 Y가 KOI 유전자라면, 이 둘을 연결한 XY도 KOI 유전자이다.주어진 DNA 서열의 부분 서열들 중에서 길이가 최대가 되는 KOI 유전자를 찾아 그 길이를 출력하시오.  - 알고리즘 정리 DP[a][b] : (s[a], s[b]) 구간에서 KOI 유전자의 최대 길이 우선 위와 같이 DP 테이블 정의를 해 줍니다. 문제에서 제시한 조건을 보면(1) KOI 유전자가 쭉 이어져 있는 경우..

- 문제 요약 주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다.정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다.n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1   (i1  n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오.  - 알고리즘 정리 평범한 LIS 문제입니다.테스트 케이스를 반복하며 구해주면 됩니다.  - 코드 작성 #includeusing namespace std;int n;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while(cin>>n){ vectorv; while(n--){ int..

- 문제 요약 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.  참고로, 세 종류의 알칼리성 용액만으로나 혹은 세 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.산성 용액과 알칼리성 용액..

- 문제 요약 세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 N이고, 세로 크기는 M이다. 또, 세준이의 집은 (0, 0)에 있고, 세준이의 학교는 (N, M)에 있다. (0, 0)에서 (N, M)까지 가는 서로 다른 경로의 경우의 수를 구하는 프로그램을 작성하시오. (세준이는 항상 최단거리로만 가기 때문에, 항상 도로를 정확하게 N + M개 거친다. 하지만, 최근 들어 이 도시의 도로가 부실공사 의혹으로 공사중인 곳이 있다. 도로가 공사 중일 때는, 이 도로를 지날 수 없다.)  - 알고리즘 정리 공사중인 도로는 배열에 따로 넣어서 체크해주고, 아래 점화식을 이용해서 문제를 해결해 주면 됩니다. dp[i][j] : (0,0)부터 (i,j)까..

- 문제 요약 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.  각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.조건 2:..

- 문제 요약 이번 ACM-ICPC 대회에 참가한 모든 사람들은 선물을 하나씩 준비했다.대회가 끝나고 난 후에 각자 선물을 전달하려고 할 때, 선물을 나누는 경우의 수를 구하는 프로그램을 작성하시오.모든 사람은 선물을 하나씩 받으며, 자기의 선물을 자기가 받는 경우는 없다.( 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. )  - 알고리즘 정리 직접 가능한 수를 만들어보며 점화식을 구해줬습니다. n = 0 (0)n = 1 (0)n = 2 (1)n = 3 (2)n = 4 (9)n = 5 (44) 이런 식으로 경우의 수를 구하며 가능한 경우를 직접 그리다 보면, 아래와 같은 점화식이 나옵니다.dp[i] = (dp[i-1] + dp[i-2]) * (i-1) 나온 값을 1,000,..