내려가기
면접 대비시간 제한1초메모리 제한4 MB
3열 N행 격자에서 인접한 열로만 이동하며 위에서 아래로 내려갈 때 얻을 수 있는 최대 합과 최소 합을 구합니다.
문제
N개의 줄에 0부터 9까지의 숫자 3개가 적혀 있다. 첫 번째 줄의 세 칸 중 하나에서 시작해 마지막 줄까지 한 줄씩 내려가는 게임이다.
한 줄 아래로 이동할 때는 현재 칸과 같은 열의 칸으로 내려가거나, 그 칸과 가로로 인접한 칸으로만 이동할 수 있다. 즉 왼쪽 칸에서는 다음 줄의 왼쪽 또는 가운데 칸으로, 가운데 칸에서는 다음 줄의 세 칸 중 아무 칸으로, 오른쪽 칸에서는 다음 줄의 가운데 또는 오른쪽 칸으로 이동할 수 있다.
방문한 칸에 적힌 숫자의 합을 점수라고 한다. 주어진 숫자표에서 얻을 수 있는 최대 점수와 최소 점수를 구하라.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 100,000)이 주어진다. 이어지는 N개의 줄에는 각 줄마다 0 이상 9 이하의 정수 3개가 공백으로 구분되어 주어진다.
출력
첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 공백으로 구분해 출력한다.