mojo's Blog

문제 링크 => 11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net) 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 다이나믹 프로그래밍 문제이다. dp 값을 어떻게 변경할 것인지에 대해서 약간 까다로운 문제인것 같다. 배열의 어떠한 값을 기준으로 왼쪽에 있는 값들과 비교해가면서 다음과 같은 조건을 만족하는 경우를 찾는다. 왼쪽의 값이 기준으로 둔 값보다 큰 경우를 찾는다. ( arr[j] > arr[i] ) 그때의 dp값..

문제 링크 => 2193번: 이친수 (acmicpc.net) 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 사실 이문제는 n=6 까지만 해봐도 피보나치의 규칙성이 보이는 단순한 문제이다. 이때 n값이 90까지이므로 int형으로 선언할 경우 틀리게 되므로 long long 을 붙여주도록 하자. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #incl..