매일 조금씩

문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 서쪽의 N개의 다리가 있고 동쪽에 M개의 다리가 있다. 다리를 겹치지 않게 배치할 수 있는 경우의 수는, 강 동쪽에서 M개의 다리 중 N개의 다리를 순서 없이 선택하는 경우의 수와 동일하다. 메모제이션 기법과 조합의 성질로 해당 문제를 풀 수 있다. 알아야 할 조합의 성질 nCn = 1, nC0 = 1 nCm = n-1Cm-1 + n-1Cm https://ko.wikipedia.org/..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP문제로, Index를 차례대로 증가시키면서 해당 Index 왼편에 올 수 있는 바이토닉 부분 수열의 최대 개수를 구한다. 이때 기준 Index에서 작은 Index를 체크하면서, 기준보다 작은 수의 바이토닉 수열 최대 개수 중에 최대 값을 구한 후 +1을 해주면 된다. 아래 문제의 왼쪽 편만 구한 것이다. ..