백준 9461
-
[java] 백준 알고리즘 9461번 파도반 수열 풀이알고리즘/백준 알고리즘 2018. 7. 21. 16:41
다이나믹 프로그래밍 문제라는 것을 감안하고 시작! 이 문제는 종이에 몇 번 끄적이다보면 규칙을 찾을 수 있다. P(10) 정도까지 만들어보겠다. P(5)까지는 규칙이 안 보여서 직접 대입했다. 해당 값(파도반 수열 P(?))이 나오는데 어떤 순서의 값들이 더해진걸까를 찾아봤다. 6번째부터는 바로 현재 삼각형의 한 변과 4번째 전에 그려진 삼각형의 한 변을 더 한 길이가 다음 삼각형의 한 변 길이가 됐다. 그럼 현재의 삼각형 길이를 구하기 위해서는 P(i) = P(i-1) + P(i-5)라는 식이 적용할 수 있지 않을까? 앞에서 말했듯이 5번째까지는 규칙이 안 보였으니 6번부터 바로 시작하겠다. P(6) == P(5) + P(1) --> 3 == 2 + 1 P(7) == P(6) + P(2) --> 4 =..