CodeDrive

문제:

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력:

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

풀이방법:

DP를 사용해서 해당문제를 풀도록 한다. 이 때, N이 6번까지는 ctrl+A,C,V를 사용하는 것보다 하나를 더 추가하는 것이 더 이득이기 때문에 하나씩 추가하도록 한다. 복사 붙여넣기를 하기 위해서는 최소 3개의 명령어를 사용해야 한다. 따라서 ACV, ACVV, ACVVV, ...와 같은 방법으로 붙여넣기를 진행할 수 있다. 하지만 붙여넣기는 최대 3번만 사용해도 최댓값을 구할 수 있기 때문에 ACV, ACVV, ACVVV 와 같은 3개 경우에 대해서 DP를 진행하도록 한다.

점화식은 dp[i] = max(dp[i-3-j]*(2*j), dp[i])와 같다.

문제링크:

https://www.acmicpc.net/problem/11058

문제:

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력:

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

풀이방법:

 이전 1, 2, 3 더하기 문제에서는 재귀형태로 문제를 풀었지만 이번에는 숫자의 범위가 크기 때문에 시간초과가 발생할 것이다. 따라서 이번에는 dp 배열을 사용하여 문제를 풀도록 한다. 

 점화식은 간단한 편이다. N을 만들기 위해서 N-3의 경우에서 3을 N-2의 경우에서 2를 N-1일 대는 1을 각각 더해주면 되기 때문이다. 즉, dp[N] = dp[N-1] + dp[N-2] + dp[N-3]과 같다.

1000000까지 dp를 만든 뒤에 N 값을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/15988

문제:

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.

이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다.

이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다.

두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최댓값은 7이다.

입력:

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1 ≤ B ≤ 2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.

출력:

얻을 수 있는 최종 점수의 최댓값을 출력한다.

풀이방법:

 DP를 사용해서 풀어야 하는 문제다. 처음에는 재귀로 이 문제를 접근했었는데, 시간초과랑 메모리 초과가 반복적으로 발생해서 반복문을 사용해서 풀게 되었다. 반복문을 사용해서 풀게 될 경우에는 정방향으로 DP를 배치하는 것이 아닌, 역방향으로 DP를 구성해야 한다고 한다. 마치 재귀로 풀이 되던 것들이 반복문으로 풀어져서 풀이 된다고 생각하면 된다.

문제링크:

www.acmicpc.net/problem/10835

문제:

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있다. 예를 들어 앞에서부터 순서대로 크기가(1,5,2,3,7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법을 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

입력:

파일의 첫 번째 줄은 상자의 개수 n(1<=n<=1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.

출력:

첫쨰 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.

풀이방법:

앞에 있는 작은 상자를 뒤에 있는 큰 상자에 넣을 수 있으므로 이는 다이나믹프로그래밍을 사용한 LIS 문제와 같다.

LIS에서 lis[i]는 i번째 수열까지 한 번에 넣을 수 있는 최대의 상자 개수이며, i+1을 추가했을 때, boxes[1]~boxes[i]까지 boxes[i+1]보다 작은 값이 있는지 파악하고, 그 수에 해당하는 lis[k] 값들 중에 최댓값에 1을 더해주는 방식으로 진행한다. 그러고 전체 lis에서 최댓값을 출력해주면 된다.

문제링크:

https://www.acmicpc.net/problem/1965

문제:

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리는 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N<=M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N,M(0<N<=M<30)이 주어진다.

출력:

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

풀이방법:

이 문제는 다이나믹 프로그래밍을 활용해서 풀 수 있는 문제이다. 

왼쪽에 3개의 사이트가 있고, 오른쪽에 5개의 사이트가 있다고 가정하자. 그럼 왼쪽의 3개와 오른쪽의 5개를 이어야 하는 문제가 된다. 하지만 왼쪽의 제일 위 점과 오른쪽의 제일 위 점에 다리를 건설했다고 하자.

이제는 아래 남은 점들은 왼쪽의 2개의 점, 오른쪽의 4개의 점을 이어야 하는 문제가 된다. 이 단계에서 한 번 더 진행하면 이제 왼쪽에는 한 개만 남고 오른쪽에는 3개, 2개 ... 가 남게 된다. 왼쪽이 1개가 되면 오른쪽에 남은 개수가 이을 수 있는 경우의 수가 되므로 이를 활용해서 점화식을 만들 수 있게 된다.

dp[i][j] = d[i-1][k-1]+d[i-1][k-2]+ ... + d[i-1][i-1]

따라서 이를 반복문으로 구현하면 다음과 같게 된다. 

https://www.acmicpc.net/problem/1010

문제:

어떤 동물원에 가로로 두 칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 불어 있게 배치할 수는 없다.

이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력:

첫째 줄에 우리의 크기 N(1<=N<=100,000)이 주어진다.

출력:

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

풀이 방법:

 dp문제인데 N마다 생성되는 규칙을 찾아내거나 아니면 점화식을 찾으면 된다. 따라서 찾은 점화식은 다음과 같다. 

an = a(n-1) + 2*a(n-2)

따라서 이 규칙에 따라서 값을 구해주면 된다.

문제 링크:

https://www.acmicpc.net/problem/1309