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

- 문제 요약 이번 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,..

- 문제 요약 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의..

- 문제 요약  첫째 줄에 학생의 수 N이 주어진다. 다음 줄에는 N명의 학생들의 점수가 나이 순서대로 주어진다. 각 학생의 점수는 0 이상 10,000 이하의 정수이다. 이 학생들을 묶어 조를 편성하려 한다. 가급적이면 실력 차이가 많이 나도록 조를 편성해야 한다. 조의 개수는 상관이 없다.각각의 조가 잘 짜여진 정도는 그 조에 속해있는 가장 점수가 높은 학생의 점수와 가장 점수가 낮은 학생의 점수의 차이가 된다. 또한 전체적으로 조가 잘 짜여진 정도는, 각각의 조가 잘 짜여진 정도의 합으로 나타난다. 한 명으로 조가 구성되는 경우에는 그 조의 잘 짜여진 정도가 0이 된다(가장 높은 점수와 가장 낮은 점수가 같으므로).학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하는 프로그램을 작성..

- 문제 요약 N명의 아이들이 임의의 순서로 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.  - 알고리즘 정리 옮겨지는 아이의 수를 최소로 하기 위해서는 현재 서 있는 줄에서 LIS를 찾고, 전체 어린이 수에서 LIS의 길이를 빼주면 됩니다.  - 코드 작성 #includeusing namespace std;#define MAX 201int n,arr[MAX],dp[MAX],mx;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=0;i>arr[i]; } for(int i=0;iarr[j] && dp[i]