1309 동물원

1309. 동물원 / c++ / Silver1 / 55분

문제 및 코드

접근 방식

동적 계획법

1. 1차 시도
   1. 동물원의 칸이 2 X N 개일 때마다, 각각 사자가 0마리 1마리 2마리 … N마리 일 때 까지의 가짓수를 다 더해보려고 했다.
   2. 규칙성을 찾지 못해서 실패 (아마 변수가 2개 [동물원의 칸, 사자의 마릿수]여서 그랬던 것 같다.)
2. 2차 시도
   1. dp 는 기본적으로 이전 값이 다음 값의 계산에 활용된다는 점에서 착안하여, 동물원의 칸이 한줄씩 더해진다고 가정했다.
   2. 규칙성을 찾게됐는데 1줄은 3줄로 나뉘면서 각각 3, 2, 2 가지의 가짓수를 갖는다.
   3. 이 규칙을 응용해서 현재 2 X Num개의 칸이 있다고 한다면, dp[Num][0] = dp[Num-1][0] + dp[Num-1][1] + dp[Num-1][1] 이고, dp[Num][0] = dp[Num-1][0] + dp[Num-1][1] 이라는 것을 알게 되었다.
   4. 3번의 공식을 DP 함수에 적용하였고, 코너 케이스를 체크하기 위해 최대 범위인 100’000을 넣었더니 에러가 떴다.
   5. dp를 재귀함수로 호출했더니 아마 스택 오버플로우가 나는 듯 했다.
3. 3차 시도
   1. 2차 시도의 알고리즘을 최적화하려고 생각해보니, 어차피 dp[Num]을 구하려면 dp[Num-1]을 알아야하는 선형 구조였다. 그래서 dp 배열과 함수를 지우고 i 가 3부터 N까지 순회하면서 계산하도록 수정했다. -> 해결

다시 생각해 볼 점

1. dp의 경우 선형이 있고, 비선형이 있는데 그걸 잘 확인할 필요가 있어보인다. 선형의 경우 최대값이 너무 크게 되면, 재귀적으로 호출할 때 스택 오버플로우가 발생할 수 있다.
2. 예전엔 어려워서 중간에 포기했던 문제인데, 시간이 좀 오래 걸렸지만 스스로 해결할 수 있어서 뿌듯했다.