https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 모든 정수를 거쳐가며 다음을 처리합니다. 첫 행은 아무 계산도 하지 않습니다 2번째 행부터 중간에 위치한 정수들은 직전 행의 오른쪽, 왼쪽 대각선의 수 중 큰 것을 더합니다. 첫 번째에 위치한 정수들은 직전 행의 첫 번째 수를 더합니다. 마지막에 위치한 정수들은 직전 행의 마지막 수를 더합니다. 계산이 끝난 후 마지막 행의 최댓값을 반환합니다. 시간 복잡도: O(N) import sys # 입력 처리하기 nums = [] # 삼각형의 크기 N = int(sys.stdi..

programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 💡 Dynamic Programming으로 풀이했습니다. 먼저 주어진 land과 같은 shape의 dp라는 리스트를 생성합니다. 이때 모든 값은 0으로 초기화합니다. dp의 두 번째 줄부터, 각 위치에 도달할 때까지의 최댓값을 dp에 저장합니다. 이때 연속해서 같은 열은 방문할 수 없게 해줍니다. cf. dp의 첫 번째 줄에선 아직까지 더해온 값이 없어 그..