https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근방식 dp 배열을 만들어서 dp[현재위치값] = 현재 위치값+ max(이동할 수 있는 위치 값) 으로 값을 갱신하며 최대,최솟값을 구한다. 처음 풀이 import sys input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] dp_max = [[0] * 3 for _ in range..
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 각 칸에 그 지점의 높이가 쓰여 있고, 각 지점의 이동은 상하좌우 이웃한 곳끼리만 가능하다. 제일 왼쪽 위칸에서 제일 오른쪽 아래칸으로 가는데 항상 높이가 더 낮은 지점으로만 이동하는 경우의 수를 구하자. 접근 방식 DP를 이용해 지나갈때마다 방문표시를 해 그 지점에 카운트를 시키며 지나가 마지막 경로에 도착시 1을 리턴하며 시작점 DP값에 증감시켜 경우의 수를 구한다. DFS를 이용해 상화좌우..