[알고리즘][다이나믹(동적 계획법) 기초] 파도반 수열 (백준)

동적 계획법 기초문제 - 파도반 수열(백준)

점화식 세우는 것이 정말 간단하다..

동적 계획법 문제를 풀 때는 항상 많은 고민을 하는데

이 문제는 딱 보자마자 점화식이 나와서 기분좋게 풀려하는데

자꾸만 틀렸다라는 문구가 나왔다..

혹시나 수가 커지면 다른 공식에 대입해야 하는 것은 아닌가.. 해서

어느정도까지 노트에 적으면서 계산까지 해봤지만 도무지 틀린 곳이 없었다..

문제는 DP배열은 int로 선언했다는 것!

N을 100으로 하면 888855064897이라는 답이 나오게 되는데

이 큰 수를 int에 넣을 수 있을리가 없다.. 이렇게 쉬운 문제가 정답률이 낮은 이유는 바로 이 때문이라 생각한다.

동적 계획법 기초 - 파도반 수열(백준)

01. 다이나믹

동적 계획법(다이나믹 알고리즘)은 코드가 짧은 대신 수학적인 사고력이 필요하기 때문에

쉬운 문제부터 차근 차근 풀어나가면서 수학적인 접근방식에 익숙해질 필요가 있다고 생각한다.

다음 포스팅부터는 난이도를 좀 더 올려서 진행해 보도록 하겠다.