빌딩 높이만 나오면 stack이 생각나서 처음에 stack으로 접근했으나 dp문제였다. A1, A2, A3, . . . , Ai, . . . An n개의 건물을 일렬로 늘어놓자. 단, A1이 가장 왼쪽, An이 가장 오른쪽이라고 가정한다. DP를 풀 때, 주관적인 주의사항 DP문제의 관건은 점화식이다. 수능 수학을 좋아했던 사람이라면, 귀납적 추론을 통한 일반항을 도출에 익숙할 것이다. DP에 사용되는 점화식을 효과적이고 효율적으로 추론하기 위해 두 가지 사항을 주의해야한다. 첫 번째 주의사항 > 반드시 n번째 항은, 이전 항(n - 1, n - 2, . . . )에 종속적으로 시행되어야 한다. 어찌보면 당연하지만, 위의 사항을 고려하지 않고 접근한다면, 잘못된 접근하거나 DP 함수를 짜기에 난이도(너무 많은 분기처리 등)가 지나치게 높아질 수 있다. 두 번째 주의사항 >초항을 제대로 고려하였는가? DP 문제에서 WA
오늘도 Junah님이 맛있는 PS 한 상을 차려주셨다. 괄호(Gold4) #DP > Junah : DP라서 살짝 어려울 수도 있지만, DP는 사고할때 작은 정답이 모여서, 큰 정답을 만드는거니까. 작은 괄호에서 큰 괄호로 만들어지는 과정을 잘 생각해보면, 쉽게 풀지도? 풀이 풀고나니 Node.js로 제출된 풀이가 3개밖에 없었다. 해당 문제를 풀기 위한 포인트는 두 가지였다. > 나열하면서 규칙을 추론하는 과정에서, 반드시 dp라는 특성을 이용할 수 있도록 이전 항을 온전히 사용할 수 있는 방법으로 경우의 수를 추론할 것. BigInt를 사용해서 계산할 것. 문제에 대한 점화식은 구했지만 25%에서 계속 WA가 발생했다. 원인은 BigInt였다. 연산하는 숫자의 뒤에 n을 붙여주면 BigInt로 바뀌게 된다. `25%에서 틀리는 선생님들은 BigInt