[ 문제 ] [ 구현 ] 성냥개비의 개수가 주어졌을 때 만들 수 있는 가장 작은 수는 DP를 통해 구했고(그리디로 가능하지만 0과 6사이의 예외처리가 머리 아플것 같음) 가장 큰 수는 그리디로 풀었다. int d[10] = { 2,5,5,4,5,6,3,7,6,6 }는 우선 각각의 숫자를 만들어내는 성냥개비의 개수를 저장한 것이다. 이를 기반으로 가장 큰 수를 먼저 생각해보면 가장 큰 수는 최대한 많은 숫자를 통해 구성해서 자릿수를 늘리는게 좋으므로 가장 적은 성냥개비를 통해 만들 수 있는 숫자인 1을 계속해서 붙이는 식으로 구성될 것이다. '1'이라는 숫자는 성냥개비가 2개 필요하므로 성냥개비의 숫자가 홀수일 경우 성냥개비가 3개 필요한 숫자인 '7'을 추가적으로 맨 앞에 활용해주면 된다. 이때 주의할 ..
[ 문제 ] [ 구현 ] VIP석이 없는 경우에 피보나치 수열의 형태로 경우의 수가 나타난다는 아이디어를 떠올리기 어려웠다. 이를 알고난 뒤, VIP석이 나타날 때마다 끊어서 VIP석 사이의 좌석의 개수에 해당하는 피보나치 수열을 ans에 계속 곱해나갔다. 맨 처음 부터 첫번째 VIP좌석까지, 마지막 VIP좌석으로부터 마지막 좌석(n번째)까지의 경우에도 알맞는 값을 ans에 곱해줄 수 있도록 VIP좌석을 관리하는 벡터에 따로 0과 n+1을 넣어주었다. [ 코드 ] #include #include using namespace std; int n, m; vector vip; int dp[41] = { 1,1 }; int ans = 1; int main() { cin >> n >> m; //필요한 피보나치 수..
[ 문제 ] [ 구현 ] 하나의 수를 제거하는 경우와 제거하지 않는 경우를 나누어서 생각해야 한다. 따라서 int dp[2][100001]의 2차원 배열을 선언 dp[i][j] -i=0일 때: 수를 하나도 제거하지 않은 상태로, arr[j]의 숫자를 포함시키며 만들 수 있는 연속된 수열 합의 최대값 -i=1일 때: 수를 한 가지 제거하면서, 만들 수 있는 연속된 수열의 합의 최대값(말로 딱 정의하기 애매하다) 점화식으로 확인하면 dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i]) dp[1][i] = max(dp[0][i - 1], dp[1][i - 1] + arr[i]) i) dp[0][i] = max(dp[0][i - 1] + arr[i], arr[i]) 우선 dp[0][..
[ 참고 ] 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 를 먼저 풀면 좋은 문제이다. [ 문제 ] [ 구현 ] N이 1000이므로 시간복잡도 O(N^2)의 이중 for문으로 풀었다. if(arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1); 의 점화식을 이용해 최대 길이를 구함과 동시에 record배열을 하나 더 만들어 dp[i]..
