정수 삼각형
-
[프로그래머스] 정수 삼각형알고리즘/프로그래머스 2021. 9. 15. 19:53
문제 링크 풀이 점화식 d[i][j]는 왼쪽 대각선 위인 d[i-1][j-1]와 오른쪽 대각선 위인 d[i-1][j] 중에서 큰 값을 triangle[i][j]와 더해준 값입니다. d[i][j] = max(d[i-1][j-1], d[i-1][j]) + t[i][j] 코드 #include #include using namespace std; int wrap(int a) { return a < 0 ? 0 : a; } int solution(vector triangle) { int answer = 0; int size = triangle.size(); vector d(size, vector(size, 0)); for (int i = 0; i < triangle.size(); ++i) for (int j = 0..
-
[백준] 1932번 정수 삼각형알고리즘/백준 2021. 8. 18. 19:17
문제 링크 풀이 이차원 배열도 일차원 배열처럼 연속된 메모리에 지나지 않지만 개발자가 작업할 때는 직관적으로 접근할 수 있어서 편합니다. 이 문제를 이차원 배열로 풀면 조금 편합니다. 예제로 주어진 입력값을 이차원 배열을 이용해 다음처럼 할 수 있습니다. 이 배열은 점화식을 위한 이차원 배열이며 dp[3][2]는 [3][2] 위치까지 합산된 최대값을 표현합니다. 즉 dp[2][1]과 dp[2][2]를 비교해서 더 큰 값을 [3][2]의 좌표의 값과 더해서 dp[3][2]를 갱신하면 됩니다. 점화식은 다음과 같습니다. d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j] 반복문 사용을 최소화하기 위해 triangle 이차원 배열을 선언하지 않고 일차원 배열을 하..