Algorithm

풀이 포도주를 먹어서 얻는 값은 모두 양수이다. 즉, 무조건 먹을 수 있으면 먹는게 이득이다. 입력값들을 arr[]에 저장한다. 그리고 동적계획법을 위한 dp[]를 만든다. dp[n]은 n번째 잔을 마지막으로 먹었을 때 가지는 최대의 점수 값이다. 하지만 n-2,n-1번째 잔까지 모두 먹은 경우는 n번째 잔을 먹을 수 없다. 즉 이번에 먹는 잔이 1.(n-2번째 잔은 먹지 않은 상태) AND (n-1번째 잔은 먹은 상태) 거나 2.(n-2번째 잔은 먹은 상태) AND (n-1번째 잔은 먹지 않은 상태) 여야 한다. 둘다 먹지 않은 상태는 위에서 쓴데로, 무조건 먹는게 이득이라고 했으니 생각하지 않는다. 즉 1번 식은 n-3번째까지 먹었을 경우의 최댓값에 n-1번째 잔과 n번째 잔을 더하고 2번 식은 n-..

풀이 숫자가 들어있는 직사각형 표가 주어진다. 그리고 주어진 표에서 직사각형모양으로 수를 선택할 때 그 직사각형 안 수들의 합을 구하라는 문제다. 반복문을 통해 그때그때 답을 구하게 된다면 큰 수가 주어졌을 때 시간초과가 날 것이다. 최대로 계산하는 경우는 1024*100,000으로 대략 10억 번이다. 그런데 문제 제한 시간은 1초로 초당 1억 번 정도 계산한다고 치면 시간초과가 나는 것이다. 그래서 우리는 이 문제를 동적계획법을 이용한 합으로 계산할 것이다. sum 배열에는 0,0 부터 그 위치를 꼭짓점으로 하는 직사각형을 그리고 그 합을 저장한다. 가령 sum[1][3]에는 arr [0][0], arr [0][1], arr [0][2], arr [0][3], arr [1][0], arr [1][1]..

풀이 수열에서 n번째 중 몇 번째에 오는지 표시하는 열과, 1~9까지의 수를 나타내는 열로 2차원 배열 arr을 만든다. 그리고 배열에는 그 번째가 그 숫자로 끝날 때의 값을 넣는다. 가령 arr [2][3] 은 2번째 자리가 3으로 끝날 때의 계단 수이다. 계단 수의 규칙에 따라, 0으로 끝났다면 앞 수는 1이어야만 계단수이다. 1로 끝났다면 앞 수는 0이나 2여야만 계단수이다. 2로 끝났다면 이전수는 1이나 3이어야만 계단수이다. 3으로 끝났다면 이전수는 2나 4여야만 계단수이다. . . . 8로 끝났다면 이전수는 7이나 9이어야만 계단수이다. 9로 끝났다면 이전수는 8이어야만 계단수이다. 즉, arr [m][n]=arr [m-1][n+1]+arr [m-1][n-1]이다. (단, n이 0이면 arr ..

풀이 피라미드 형태의 문제 그대로 배열을 만들면 된다. 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