[알고리즘] 백준 파이썬 2096 내려가기

📍 문제 탐색하기내려가기 성공 문제는 N줄에 0 이상 9 이하의 숫자가 세 개씩 주어진 배열에서 첫 줄에서 시작해 마지막 줄까지 내려가며 얻을 수 있는 최대 점수와 최소 점수를 구하는 문제다.현재 위치에서 바로 아래의 숫자 또는 인접한 숫자로만 이동할 수 있다.점수는 이동한 위치의 숫자의 합으로 계산된다.입력 범위N: 1 ≤ N ≤ 100,000각 줄에 주어진 숫자: 0 ~ 9시간과 메모리 제약을 고려해야 한다.가능한 시간복잡도최대 N=100,000에서, 각 줄마다 최대 3개의 숫자를 탐색하므로, O(N) 시간 복잡도로 해결해야 한다.이를 위해 동적 계획법(DP)을 사용해 각 위치에서 얻을 수 있는 최대 및 최소 점수를 효율적으로 계산한다.알고리즘 선택동적 계획법(DP)을 사용한다.한 줄의 숫자만 메모..
알고리즘 2025. 1. 13. 23:58
1