알고리즘

풀이 피라미드 형태의 문제 그대로 배열을 만들면 된다. n에는 높이, m에는 수평개수가 들어가는 arr [n][m] 배열을 만든다. n에는 높이, m에는 수평개수가 들어가는 dp[n][m] 배열도 만든다. dp [0][0]에 점화식을 위한 처음값 arr [0][0]을 넣어준다. 그리고 dp[n][m]에 dp [n-1][m]과 dp [n-1][m-1] 중 큰 값을 고르고 arr [n][m]을 더해 할당한다. 이때 인덱스가 최소 최대 범위를 넘지 않도록 조심한다. 그리고 마지막 dp[n]에서 배열들 중 최댓값을 출력한다. 해답 코드 #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace s..

풀이 문제를 해석해보자, 일렬로 된 집이 있다. 그런데 양 옆집과는 같은 색이면 안되며, 색을 칠하는 비용은 집마다 색깔마다 각기 다르다. 이때 최솟값을 구하라는 문제이다. 많은 경우의 수를 생각해야 한다. 색깔이 3개이니 [집의 수][3] 인 이차원 배열을 만든다. 그리고 각 dp[n][m]에는 n번째 집에 m번째 색깔을 칠했을 때 나올 수 있는 최솟값을 넣는다. dp[n][m]은 dp[n-1][m이 아닌 다른 값] 에 비용을 더하면 된다. 이전 입력된 배열들을 바탕으로 다이나믹 프로그래밍으로 풀면 된다. 하위 배열에서 입력된 값에 근거하기 때문이다. 해답 코드 #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(..

풀이 입력된 수열들을 arr []에 저장한다. 다이내믹 프로그래밍으로 dp [n]에 n번째 원소를 마지막으로 취할 때의 길이를 저장한다. 그리고 dp 배열에서 최댓값을 찾으면 된다. 그러면 dp[n]은 어떻게 찾을 수 있을까? 입력을 받을때마다, 이전 배열값들을 탐색한다. n> m일 때, arr [m]>n; int arr[n]; int dp[n]; cin>>arr[0]; dp[0]=1; for(int i=1; i>arr[i]; beforemax=0; for(int j=0; j

풀이 함수의 규칙에 따라 재귀함수로 출력해야 한다. 재귀함수로 출력하되, 이미 저장된 값은 동적계획법으로 바로 출력할 수 있게 하면 된다. 하지만, 이 문제에서는 재귀함수 말고 반복문을 통한 동적계획법으로도 출력이 가능해 재귀함수를 사용하지 않는 방식으로 풀었다. 비슷한 문제가 나올 경우, 재귀함수를 이용해 푸는 것을 추천한다. 해답 코드 #include #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int arr[101][101][101]; int main(){ int a=1,b=1,c=1; while(!(a==-1&&b==-1&&c==-1)){ cin>>a>>b>>..

풀이 이항계수 공식을 이용해야 한다. N과 K를 공식으로 쓰면 nCk = nC(k-1)+(n-1) C(k-1)가 나온다. 즉, 초깃값부터 다이나믹 프로그래밍으로 풀어야 한다. 단 여기서, 10007로 나눈 나머지를 원했으므로 숫자 범위 추가를 조심해야 한다. 해답 코드 #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main() { fastio; int dp[1001][1001]={0}; unsigned int n,r; cin>>n>>r; for(int i=1;i

풀이 입력되는 수열들을 arr [n]이라고 하자. 연속된 arr[n]의 합 중 가장 큰 것을 구해야 한다. 이를 위해 arr[n]을 보고 동적계획법으로 값을 결정하는 수열을 dp [n]이라고 하자. dp [n]은 arr [n]을 마지막 원소로 하는 최댓값이 되는 수열이다. 수열의 당장 다음값이 음수더라도 그 수열을 끊지 않고 이어갔을 때 절댓값이 더 큰 양수들을 얻을 수 있다면 수열을 이어나가야 한다. 그렇다면 어떻게 이것을 판단할 수 있을까? 일단 새로운 값이 나오면 음수더라도 더하되, 현재까지 dp[n]의 값이 음수라면 그냥 새로운 arr[n]값부터 새로 시작하면 된다. 이미 합이 음수가 되어버린 dp[n]은 더이상 답이 될 수 없다. 그냥 새로운 arr[n]부터 시작하면 된다. dp [n-1]에서 ..

풀이 새로 생겨나는 큰 삼각형들의 한 변의 길이는 이전 삼각형들의 두변의 길이의 합니다. 쭉 나열해보면 6번째는(흰색 3) = 5번째(파란색 2)+1번째(파란색 1) 7번째는(파란색 4)=6번째(흰색 3)+2번째(흰색 1) 8번째는(흰색 5)= 7번째(파란색 4)+3번째(파란색 1) 9번째는(파란색 7)=8번째(흰색 5)+4번째(흰색 2) 10번째는(흰색 9)=9번째(파란색 7)+5번째(파란색 2) 11번째는(파란색 12)=10번째(흰색 9)+6번째(흰색 3) 어떤 삼각형의 한편 길이는 바로 직전의 삼각형과 5번째 전의 삼각형 한변 길이의 합임을 알 수 있다. 따라서 n번째 삼각형의 한 변의 길이를 arr [n]이라고 할 때 arr [n]= arr [n-1]+arr [n-5]라고 할 수 있다. n-5부터..

입력 입력의 첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300 이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000 이하의 자연수이다. 풀이 입력조건에 중요한 단서가 있다. 계단에 써져 있는 수는 모두 자연수다. 즉, 계단은 밟을 수 있다면 밟는게 일단 이득이라는 뜻이다. 하지만 3연속으로 밟을 수는 없으니 더 큰 점수를 위해 때로는 연속으로 가지 말아야 한다. 계단에 각 숫자가 몇이 써져 있는지 나와있는 입력배열을 arr [n] n번째 계단까지 올랐을 때 얻게 되는 점수의 최댓값 배열을 sum [n]이라고 하자. sum [n]은 1. sum [n-2]+arr [n] (n-2번째 계단의 최대..