문제 이해 단계 https://www.acmicpc.net/problem/1890 각 칸마다 이동해야 하는 칸 수가 적혀 있고, 가장 왼쪽 위 칸에서 오른쪽 아래 칸으로 이동해야 한다. 즉, 해당 칸에 도착했을 때 0이면 움직임이 멈춘다.(더 이상 이동하지 못하기 때문) 할 수 있는 움직임은 아래로 이동하거나 왼쪽으로 이동하거나 2가지이다. 이러한 조건일 때 가장 오른쪽 아래로 이동할 수 있는 경우의 수를 구하는 문제. 문제 접근 단계 가장 오른쪽 아래로 이동할 수 있는 경우의 수를 구하는 것이기 때문에 오른쪽 아래에서부터 역으로 출발하는 걸로 생각했다. 게임판의 크기가 NxN일 때, 마지막 칸으로 움직일 수 있는 경우는 무엇이 있을까? 그림으로 생각해 보면 이런 식이 될 것이다. 이런 식으로 마지막칸에..

이해 단계 수열 문제 시리즈이다. 수열이 주어질 때 증가하는 부분 수열을 원소들을 찾는다. 그 원소들의 집합 중 합이 가장 큰 집합을 찾아 그 값을 찾아내는 문제이다. 문제 접근 단계 가장 큰 수열 ~ 문제 시리즈 상 문제를 읽지 않아도 DP로 풀어야겠구나라고 생각이 바로 들더라.. 이러면 안 되긴 하는데 너무 문제가 시리즈상으로 많이 있어서 자연스럽게 그렇게 됐다.. 그래도 이 문제가 왜 DP로 풀 수 있는지 따져보기로 했다. 이 문제의 예제로 살펴보도록 하자. {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 왼쪽부터 x = 1이라고 해서 순차적으로 올라가 보면서 생각해 보겠다. x = 1 일 때 최댓값은 1이다. x = 2 일 때, (1)(1+100)(100) 중, 최댓값은 101이다...

문제 이해 단계 수열이 주어졌을 때 위치를 가만히 둔 채로, 오름차순으로 증가하는 부분 수열은 구한다. 그때 가장 크게 증가하는 부분수열의 길이를 구하는 문제 문제 접근 단계 문제에 나와있는 예시로 생각해 보자 10 20 10 30 20 50 1번째 수(10)에서 가장 긴 부분수열의 길이는 1이다. 2번째 수까지의 경우의 수는 3가지이다. 1. 10 - 20 (2가지) 2. 20 (1가지) 3. 10 (1가지) 이때 가장 긴 부분수열은 1번째인 2이다. 3번째 수까지의 경우의 수는 1. 10 - 20 (2가지) 2. 20 - 10 (2가지) 3. 20 ... 로 2번째보다 길어지려면 20보다 수가 높아야 하는데, 그렇지 못하므로 그대로 최대 길이는 2이다. 4번째 수까지의 경우의 수는 1. 10 - 20..

문제 이해 단계 N의 길이를 가진 수열에서 최대 K개만큼 원소를 삭제할 수 있을 때, 최대한 많이 짝수끼리 연속되게 만드는 문제이다. 그때의 개수를 구하는 문제이다. 문제 접근 단계 처음에는 1차원에다가, 짝수와 홀수를 구분하여 탐색하는 BFS를 떠올렸다. 그런데 일반적인 탐색으로 하기에는 제거할 홀수의 경우의 수가 너무 많다. 그리고 그 경우의 수를 모두 체크하기엔 너무 연산이 복잡하고 또 시간이 오래 걸린다. 또한 여기서는 어떤 시작 인덱스나 숫자를 정해주지 않아서 그것 또한 찾아야 하기 때문에 이 방법은 어울리지 않는다고 생각했다. 그다음으로 떠올린 것은 다이내믹 프로그래밍이다. 왜냐하면 이런 제한시간이 짧고, 많은 경우의 수가 있는 경우에는 충분히 가능성 있기 때문이다. 연속된 짝수를 계산하기 위..

문제 이해 단계 수학에서 조합을 뜻하는 nCr에서 n과 r이 입력으로 들어올 때, 그 해답을 출력하는 문제. 문제 접근 단계 일반적으로 연산식을 구현하여 계산하라고 이 문제를 냈을 리는 없다. 예제에서 봤듯이 입력애 따라 출력이 엄청 커지는데, 연산 처리가 오래 걸려 시간초과가 뜰 가능성이 높다. 그래서 조합 공식 nCr = n-1Cr + n-1Cr-1을 메모라이즈기법(DP) 방식으로 구현하기로 하였다. d [n][m]라는 2차원 저장공간을 두고 nCr = d [n][r] 이런 식으로 연산 값을 기억해 두기로 하였다. 그런데 한 가지 문제가 생겼다. 바로 연산 값이 엄청나게 크다는 것이다. 가장 큰 자료형인 long long int가 –9,223,372,036,854,775,808 ~ 9,223,372,..

문제 이해 단계 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다. 자연수 n이 주어질 때, 최소 개수의 제곱수 합, 즉 최소한의 자연수를 사용하여 구하는 문제이다. 문제 접근 단계 제곱수라는 말과 반대되는 말은 루트이다. 4 = 2^2인데, 이때 제곱이 되는 2라는 값은 4의 루트를 씌우면 구할 수 있다. 여기서 5라는 값을 살펴보면 5의 루트를 씌우면 2.xxx 자연수 부분은 2가 된다. 해당 문제에서는 5 = 2^2 + 1^2가 되어 2가 출력될 것이다. 이런 식으로 n에다가 루트를 씌어 하나의 제곱수를 구하고, 그 수를 뺀 나머지를 또 루트를 씌우는 과정을 반복한다면? 우리는 제곱으로만 이루어진 수의 합을 구할 수 있을 것이다(1^2이 있기 때문) 15라는 숫자를 예로 들어, 그림..

문제 이해 단계 https://www.acmicpc.net/problem/2579 입력으로 계단의 개수가 주어지고, 그다음부터 각 계단의 점수가 순서대로 주어진다. 출발부터 시작하여 마지막 계단까지 이동하는데 2가지 규칙을 따른다. 1. 이동은 1칸 또는 2칸을 이동한다. 2. 1칸을 이동할 때는 연속되는 3칸을 이동할 수 없다(1,2,3 이런 식) 이런 조건에서 마지막 칸까지 이동할 때 얻을 수 있는 최대 점수를 구하는 문제이다. 문제 접근 단계 마지막 계단을 무조건 밟아야 하기 때문에 마지막 계단부터 생각해 보자. 마지막 계단으로 도달할 수 있는 경우의 수는 2가지가 있다. 1. 1칸 이동했을 때 2. 2칸 이동했을 때 그런데 우리가 구해야 하는 것은 마지막 계단에 도착했을 때의 최대 점수이다. 때문..

문제 이해 단계 https://www.acmicpc.net/problem/1010 N과 M이 주어진다. N = x; i--) { result += dp(x - 1, i - 1); } d[y - x][y] = result; return d[x][y] = result; } 핵심이 되는 dp함수이다. 매개변수로 N, M을 뜻하는 x, y를 받는다. 2차원 배열 저장공간 d [][]를 사용하여 해당 경우의 수를 저장해 놓는다. long long int로 선언한 이유는 값이 엄청나게 커질 수 있기 때문에 오버플로우 발생을 방지하기 위해서이다. 우선 빠른 연산을 위해 N이 1이 경우와 N과 M이 같을 경우는 연산이 쉬우므로 그 결과는 바로 배열에 담아 반환한다. 그리고 이미 연산결과가 있는 경우에는 계산하지 않고 ..