2096번: 내려가기

Difficulty : Gold V

Problem Description

There are N lines and three numbers in each line.

You have to start from the first line to the last line.

When you go down to the next line, you have to choose the number which is just below or right next to your below.

The output is the maximum sum and the minimum sum.

 

Solution

I solved this problem by dividing the sum into three cases.

The last number is left, middle, or right.

 

Get the number of lines, and make two lists for max, min and set the initial value.

 

Mini has three values which are means the sum which ends with x, y, z.

If the sum ends with x, previous value must be left or middle. So find the smaller sum with them.

If the sum ends with y, previous value must be left, middle or right.

If the sum ends with z, previous value must be right or middle.

Calculate the maxi with the same way of mini.

 

Today's Code

import sys; sys.stdin.readline() : input()과 같은 역할이지만 속도가 훨씬 빠름

a = lambde : f(x) : a가 f(x)의 함수 역할을 함

 

여담

처음에 input()을 사용해서 제출을 하였더니 문제가 해결되긴 했지만 시간이 4000ms가 넘어 상당히 오래 걸렸다.

 mini와 maxi도 원래는 시간초과로 인해 리스트를 사용하지 못하고 minL, minM, minR과 같이 변수를 하나하나 설정해 뒀었다. 문제를 풀고 나서 시간이 빠른 다른 코드들을 둘러보니 알고리즘 자체는 본인과 동일했지만 입력받는 명령어 딱 하나가 달라서 시간차이가 발생했고 검색을 통해 속도 차이가 발생한다는 사실을 알게 되었다.