Jumping on the Clouds

오랜만에 문제를 풀면서 간단하지만 쉽게 풀지 못했던 문제가 있었다. 결국 시간적으로 너무 오래 걸리는 것 같아 답을 찾아보았고 여러가지 것들을 배울 수 있었던 문제였다.

DP

가장 먼저는 DP를 생각해내지 못했다. 경우의 수가 있고 그것들을 비교해서 최적값을 가져간다는 생각은 있었지만 선형적으로만 생각했지 메모이제이션에 대해서는 떠올리지 못했다.

배열의 크기 조절

평소에 배열을 다루면서 i+1, i+2 따위로 인덱스를 찾았는데 이렇게 하면 항상 마주치는 것이 ArrayIndexOutOfBound exception이었다. 볼 때마다 어떡하지 했었는데, 다음과 같은 두가지 방법으로 해결하면 된다는 걸 알았다.
1. 문제에 주어진 배열의 최대값보다 더 큰 배열을 만들면 된다.
2. dp를 사용하면 현재 인덱스는 유지되고 그것보다 작은 인덱스만 찾기 때문에 배열 크기를 넘어서지 않는다.

배열의 시작 위치 조절

DP를 쉽사리 떠올리지 못했던 이유가 바로 이것인데, 시작 지점이 0이거나 1인 경우가 각각 다르기 때문에 첫 조건을 어떻게 걸어야할지 고민이 되었다. 직관적으로 넣어줄 수도 있지만 그러면 코드가 굉장히 더러워질 수 있었고, 이것은 “배열의 시작점을 0이 아닌 1로 둔다”는 방법으로 해결할 수 있었다. 전혀 생각하지 못했던 사고의 전환이다. 다음번에는 적용할 수 있도록 꼭 명심해야겠다.

자바 배열의 값 초기화

사소하지만 중요한 것인데, 문제를 풀면서 dp 메모이제이션에 쓸 int 배열의 값을 모두 0으로 초기화 해주는 코드를 넣었었는데, 결과적으로 이건 필요가 없었다. 자바에서 int 배열을 선언하면 자동으로 0이 채워진다.
기본 언어 지식인데 간과하고 있었다.

 

오랜만에 문제를 푸는만큼 쉬운 문제부터 접근한다고 생각했는데 실제로 푸는 방법은 그렇게 쉽지는 않았던 것 같다. 좀 더 정신차려서 다양하게 접근하는 시도를 해야겠다.