[ MR 03. 프로그래머스 - 정수 삼각형 ]
Making Routine Series : MR
03. 프로그래머스 : 정수 삼각형
언어 : C++
SWEA,백준,프로그래머스 3개 돌려서 합니다!
주말제외 1일 1개씩 푸는 습관 길들이기 하는 중입니다!
따라서 도움이 안되실 수 있습니다...
같이 푸는 습관은 만들 수 있어요...! ㅎㅎ
문제
문제 설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중,
거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다.
아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.
예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때,
거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.제한사항
삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
입출력 예제
내 풀이
동적 계획법(Dynamic Programming, DP)을 사용해서 각 지점에서 가능한 최대 경로 합을 저장하면서 아래로 내려가기. 이미 방문한 경로의 최대 합을 재사용하여 계산량을 줄이는 줄이기.
접근 방법
삼각형의 맨 아래부터 시작: 맨 아래 행부터 시작하여 위로 올라가면서
각 위치에서 가능한 최대 합을 계산하기.DP 배열 사용: 주어진 삼각형 배열 자체를 DP 배열로 사용하여
원본 배열을 갱신하는 방식으로 최대 합을 저장하기.
단계별 해결 방법
입력 받기: 삼각형 배열을 입력으로 받습니다.
맨 아래 행부터 시작: 맨 아래 행의 값은 그대로 둡니다.
위로 올라가며 값 갱신: 삼각형의 각 원소에 대해,
현재 위치에서 가능한 두 경로 중 더 큰 값을 선택하여 자신의 값에 더해줍니다.꼭대기 값 반환: 최종적으로 꼭대기의 값이 최대 경로 합이 됩니다.
핵심 코드
// 맨 아래 행부터 시작하여 위로 올라감
for (int i = n - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
// 아래 행의 왼쪽 및 오른쪽 요소 중 큰 값을 현재 요소에 더함
triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
}
}후기
생각보다 원리 파악만 하면 쉽게 풀었을 문제...!
코테 UI는 프로그래머스가 제일 이쁨..(프로그래머스 최고...
