아이디어 처음엔 삼각형의 위에서부터 1층, ..., k층, ..., n층으로 생각하고 k층까지의 최적의 경로가 n층까지의 최적의 경로에 포함될 것이라 생각할 수도 있다. 그러나 예시로 주어진 테스트케이스가 그 반례이다. 따라서 최적의 경로는, 2차원배열의 각 인덱스에 해당하는 dp[i][j]에 저장되어있다. 그러므로 dp[i][j]에 도달하는 optimal한 경로와 dp[i][j+1]에 도달하는 경로가 다를 것이다. dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j]; 를 사용하여 해결하면 된다. 다시 말하자면, k층까지 탐색했을 때 합이 최대가 되는 것이 최적의 경로가 아니라, k층의 l열을 오는 데에 합이 최대가 되는 경로가 최적의 경로(dp의 점화식)을 구..

수의 규칙을 보고 떠오르는 점화식을 적었다. dp[MAX] 배열에 저장했다. 자료형이 long long이 되어야 함에 유의하자. #include using namespace std; using ll = long long; const int MAX = 105; int n,t; ll dp[MAX]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); dp[1] = 1; dp[2] = 1; dp[3] = 1; for (int i = 4; i > t; while (t--) { int n; cin >> n; cout

연쇄 행렬 곱셈 일반적으로, i * j 행렬과 j * k 행렬을 곱하면 원소단위 곱셈의 실행 횟수는 다음과 같다. i * j * k 번 실행 횟수가 행렬의 크기에 따라 결정된다. 따라서 최적의 순서도 행렬의 크기에만 의존한다. n개의 행렬 \({A}_{1}\) ... \({A}_{n}\))을 곱하는 모든 순서의 가지 수를 \({T}_{n}\)이라고 하자. A1을 마지막으로 곱하는 순서의 집합의 가지수는 \({T}_{n-1}\)이다. (A_1...A_n까지 곱하는 서로 다른 순서의 가지수) An을 마지막으로 곱하는 순서의 가지 수 또한\({T}_{n-1}\)일 것이다. 따라서 다음과 같은 부등식이 나온다. $$T_n >= T_{n-1} +T_{n-1} = 2 * T_{n-1}$$ 두 개의 행렬을 곱하는 법..

이해 수학 문제다. Josephus problem은 wiki에도 잘 나와있다. https://en.wikipedia.org/wiki/Josephus_problem Josephus problem - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search In computer science and mathematics, the Josephus problem (or Josephus permutation) is a theoretical problem related to a certain counting-out game. A drawing for the Josephus problem en.wikipedia.org 1에서 인..

이해 입력 D의 범위 안에서 최대 점수('현재 점수 * 다음 점수'의 합)을 구한다. 입력받은 2차원 배열과 같은 크기의 dp[i][j]를 만들자. dp[i][j]가 i행 j열 까지의 최대 점수라고 할 때, dp[i][j]는 i행 j열로 가기 전 단계 x행 y열에서, 'x행 y열의 점수 * i행 j열의 점수' 연산을 더하는 값과, 더하지 않는 값 중의 최댓값이다. 따라서 dp[i][j] = max(dp[i][j], dp[x][y] + cur*next); 라는 점화식을 떠올리는 것은 쉽다. 틀렸습니다 70%쯔음에서 '틀렸습니다'를 받았다면 INF(dp배열 또는 답의 초기값의 최저)의 값을 너무 낮게 설정했을 수 있다. 메모리 초과가 났다면 입력의 2차원 배열을 int arr[100001][100001]로 ..