부녀회장이 될테야 0.5 초 (추가 시간 없음)128 MB104395590145008757.510% 문제평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.입력첫 번째 줄..

핸드폰 번호 궁합 2 초256 MB35332684238377.622%문제어린시절 다들 한 번씩은 이름으로 궁합을 본 적이 있을 것이다. 이것과 비슷한 방식으로 중앙대학교에는 핸드폰 번호 궁합을 보는 것이 유행이라고 한다.핸드폰 번호 궁합을 보기 위해서는 먼저 궁합을 보고싶은 두 중앙대생 A와 B의 핸드폰 번호에서 맨 앞의 010과 "-"(하이픈)을 모두 제외한 후, A부터 시작하여 한 숫자씩 번갈아가면서 적는다. 그리고 인접한 두 숫자끼리 더한 값의 일의 자리를 두 숫자의 아래에 적어나가면서 마지막에 남는 숫자 2개로 궁합률을 구하게 된다.예를 들어, 아래의 그림과 같이 A의 번호가 010-7475-9336 이고, B의 번호가 010-3619-5974 이면, 7346715995393764에서 시작하여 0..

가장 긴 증가하는 부분 수열1 초256 MB169140679584509838.082%문제수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.예제 입력 1 복사610 20 10 30 20 50예제 출력 1 복사4가장 긴 증가하는 부분 수열(LIS, Longest Incr..

동적 프로그래밍(Dynamic Programming, DP) 알고리즘은 문제를 작은 하위 문제들로 나누어 해결한 다음, 그 결과를 결합하여 원래의 문제를 해결하는 기법입니다. DP는 주로 다음 두 가지 특징을 가진 문제에 사용됩니다:중복되는 하위 문제:동일한 하위 문제가 여러 번 반복해서 계산되는 경우.최적 부분 구조:문제의 최적 해가 하위 문제들의 최적 해로 구성될 수 있는 경우.DP 알고리즘은 크게 두 가지 방식으로 구현됩니다:탑다운(메모이제이션, Memoization):재귀를 사용하여 문제를 푸는 방식입니다.이미 계산된 하위 문제의 결과를 저장해두고, 동일한 하위 문제가 다시 등장할 때 저장된 값을 재사용합니다.이 방식은 재귀 호출로 인해 스택 오버플로우가 발생할 수 있으므로 주의가 필요합니다.바텀..