/* 맨 위층 아래층으로 내려올 때, 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하세요. 대각선왼쪽 또는 대각선오른쪽에 있는 수를 선택가능합니다. 삼각형의 크기는 1이상 500이하. 오케이 삼각형의 크기가 주어지고 오케이 이것은 구현가능합니다. */ #include <iostream> #include <algorithm> using namespace std; int N; int numArr[501][501]; int d[501][501]; int maxVal=0; void problemIn() { cin >> N; for (int i = 1; i <= N; i++) { for (int j = 1; j <= i; j++) { cin >> numArr[i][j]; } } } /* i= 3 j =2 */ void solve() { for (int i = 1; i <= N; i++) { for (int j = 1; j <= i; j++) { if (j == 1) { d[i][j] = d[i - 1][j] + numArr[i][j]; } else { d[i][j] = max(d[i - 1][j - 1], d[i-1][j]) + numArr[i][j]; } } } //for (int i = 1; i <= N; i++) { // for (int j = 1; j <= i; j++) { // cout << d[i][j] << " "; // } // cout << endl; //} for (int i = 1; i <= N; i++) { if (d[N][i] > maxVal) maxVal = d[N][i]; } cout << maxVal << endl; } int main(void) { problemIn(); solve(); return 0; } |
규칙을 찾아서 배열에 저장하는 것입니다. 2차원 배열을 사용할 때 주의할 점은 행렬의 인덱스밖에 없습니다. 규칙을 찾아서 저장하는 방법에 대해서 전체적인 것을 보는 것이 아니라, 하나씩 하나씩 보도록 합니다. 잘게 쪼갠다음에 문제 풀이를 하도록 합니다. |