SSAFY대비_CT_예상문제풀이_이동하기

알고리즘 잡스에서 다룬 8기 대비를 위한 예제 문제이다.

https://www.youtube.com/watch?v=UsTo-0hAb6k&t=5s

문제는 다음과 같다.

이전에 다룬 이상한 음식점 문제와 유사하다고 느꼈다. 하지만 풀이 방식에 차이가 있다.

오른쪽과 아래 방향으로만 이동할 수 있다. 즉 1행에서 가능한 최대 점수를 얻고 2행으로 이동하여 2행에서 최대 점수를 얻어야 될 것이다.

처음 문제를 풀었을 때 분명 풀이방식이 있지 않을까 생각했지만 그 풀이방식을 바로 알 수 없기 때문에 대충 어림짐작하여 가장 최대 숫자를 얻을 수 있을 것 같은 숫자들을 적은 후 최종적으로 숫자들을 모두 더하여 답을 계산하는 방식으로 문제를 풀었다.

문제를 풀고 난 뒤에 알고리즘 잡스 강의에서 역시 해당 문제에 대한 풀이 방법을 설명해주었다.

1행은 왼쪽으로부터 각 숫자들을 차례로 더해가며 더하기 연산 결과를 그 차례의 숫자 위에 적어 놓고 2행은 오른쪽으로 부터 왼쪽으로 이동하며 같은 방식으로 숫자들을 아래에 적었다.

그렇게 1행 위, 2행 아래에 적힌 숫자들에 대해 각 열에 해당하는 두 숫자를 더한 결과를 적으면 그 중 가장 큰 수가 정답이 되게 된다.
(이상한 음식점 문제에서 LIS정방향과 LIS역방향을 각각에 열에 대해 구한 후 두 값의 합이 가장 큰 수를 고른다는 점이 같았다.)

결론적으로 풀이 방법을 듣기 전에 나의 풀이방식과 비교했을 때 해당 방법이 훨씬 빠르고 정확하다는 것을 알 수 있었다.