2156번 포도주 시식, 11053 가장 긴 증가하는 부분수열
코딩테스트 : 2156번 포도주 시식
문제
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.
예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.
입력
첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.
출력
첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.
using System.Runtime.Intrinsics.Arm;
public class BackJoon
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] arr = new int[n + 1];
for (int i = 1; i <= n; i++)
{
int temp = int.Parse(Console.ReadLine());
arr[i] = temp;
}
Console.WriteLine(DP(n,arr));
}
public static int DP(int n, int[] arr)
{
if (n == 1) return arr[1];
if ( n == 2) return arr[1] + arr[2];
if ( n == 3) return Math.Max(arr[1]+ arr[2], Math.Max(arr[1] + arr[3], arr[2] + arr[3]));
int[] dp = new int[n + 1];
dp[1]= arr[1];
dp[2] = dp[1] + arr[2];
dp[3] = Math.Max(dp[2], Math.Max(arr[1] + arr[3], arr[2] + arr[3]));
for (int i = 4; i <= n; i++)
{
// dp[i-1] 안마시는 경우
// dp[i - 3] + arr[i - 1] + arr[i] 바로 마시는 경우
// dp[i -2] + arr[i] 한 칸 쉬고 마시는 경우
dp[i] = Math.Max(Math.Max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 1]), dp[i - 2] + arr[i]);
}
return Math.Max(dp[n],dp[n-1]);
}
}
점화식...을 잘 생각하자, 저번 문제랑 같지만(계단) 정확하게 마지막 포도주를 마실 필요가 없다.
코딩테스트 : 11053 가장 긴 증가하는 부분수열
| 1 초 | 256 MB | 191520 | 77691 | 51521 | 38.393% |
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
public class BackJoon
{
public static void Main()
{
int n = int.Parse(Console.ReadLine());
int[] arr= Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
Console.WriteLine(DP(n,arr));
}
public static int DP(int n, int[] arr)
{
// (count, number)
(int,int)[] dp=new (int,int)[arr.Length];
if (n == 1) return 1;
dp[0] = (1, arr[0]);
for (int i = 1; i < n; i++)
{
int tempNumber = arr[i];
int maxCount = 0;
for (int j = 0; j < i; j++)
{
if(dp[j].Item2 < tempNumber)
{
if (dp[j].Item1 > maxCount)
{
maxCount = dp[j].Item1;
}
}
}
dp[i] = (maxCount+1,tempNumber);
}
return dp.Max(x => x.Item1);
}
}
이것도 마찬가지로... 전체에서 답을 찾아야 한다.
물론 dp.Max로 찾는 것보다 더 효율적으로 하려면 변수 하나 더 추가해서 해도 될 것 같다.
들어오는 n이 1000이라서 이렇게 반복문 두 개를 사용해서 풀었다.
1000 * 1000이면 그렇게 큰 반복은 아니라고 생각했다.
다만 반복을 사용하지 않고도 풀 수 있는 방법이 있는지 다른분들의 코드를 살펴봐야겠다.
다른 사람의 흥미로운 풀이
지금은 모든 배열을 반복해가면서 더 낮은 숫자를 찾고 있지만 ,
이를 개선하기 위해서 이미 C#에 제공되어 있는 이진탐색 기능 (BinarySerch)와 같은 기능을 사용해서
dp[j].Item2 < tempNumber를 찾는다면 시간복잡도가 상당히 개선된다.