- 문제 요약 세준이가 살고 있는 도시는 신기하게 생겼다. 이 도시는 격자형태로 생겼고, 직사각형이다. 도시의 가로 크기는 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]

- 문제 요약 첫째 줄에는 이번 시험의 단원 개수 N(1(단, 여러 단원을 융합한 문제는 출제하지 않는다. 한 단원에 한 문제를 출제하며, 어떤 단원의 문제를 맞추기 위해서는 그 단원의 예상 공부 시간만큼, 혹은 그보다 더 많이 공부해야만 맞출 수 있다.)  - 알고리즘 정리 냅색 문제입니다. dp[x] = max(dp[x], dp[x-(예상 공부 시간)] + (문제 배점의 최대값))위 점화식을 사용하여 해결할 수 있습니다.  - 코드 작성 #includeusing namespace std;#define MAX 10001int n,t,dp[MAX],arr[101][2];int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);..