https://www.acmicpc.net/problem/9461
Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net이 좆같은 삼각형이 좆같은모양으로 늘어나는데, 규칙을보니 새로생길 삼각형은 바로전 삼각형 ( n-1) 과 5번째전 삼각형 ( n-5) 길이의 합임
1 1 1 2 2 3 "4" 5 7 9 "12" 다음 삼각형은이제 12 + 4 = 16 임
그러면
이럼걍 1부터 10까지 값 지정해두고 n - 1 , n- 5 합쳐서 반환하면 끝아님 ?
이제3주되서 모름 걍 저렇게 규칙찾아서 때려박는중 그와중에 long long인데 int로했다가 5번틀림
잘하고 있습니다
와정말요
dp 처음 배울때는 점화식 세우는게 굉장히 어렵다고 생각합니다 굿이에요
굿.. 맞음. 근 x-1번째, x-5번째까지 성립되어 있다고 가정하면, x번째가 성립됨을 보인거잖아. x일때 성립함을 보이기 위해 x-1과 x-5가 성립한다는 사실에 의존했고 n>=1이니까 x=1~6까지가 base case가 됨. 그래서 6까지만 미리 계산해도 됨.
와맞네
잘했네 나도 저 발상을 못했는데 ㅋㅋ
해당 댓글은 삭제되었습니다.
저게 그림덕분에, 삼각형 변두개 합쳐져있는거보고 바로눈치챔 다른문제면 식구하는거에 몇시간더걸릴듯 ㅜ
n = n-2 + n-3 = (n-4 + n-5) + n-3 = (n-3 + n-4) + n-5 = n-1 + n-5 원래 파도반 수열의 정의는 n-2 + n-3이긴함 - dc App
아니 이것도 이미 정의되있는 뭔가 저명한 그런거였구나
내맞워요
참고로 저거 행렬 거듭제곱으로 푸는 방식 피보나치 문제에서 많이 써먹으니까 알면 레이팅 날먹 가능해오