문제 링크입니다.
https://www.acmicpc.net/problem/2482
풀긴했는데 dp차원을 4차원으로 써서 메모리 낭비가 너무 심해서 어떻게 줄일까 고민하던중
(https://www.acmicpc.net/board/view/47224 제 코드입니다)
맞은 분 코드중에서 사진과 같은 코드를 봤는데 원래 탑다운으로만 풀던 저라 코드파악을 한줄도 못하겠어요 ㅠ
슬랙에도 백준에도 질문 올렸지만 딱히 답변이 없어 마지막으로 도움요청해봅니다 ㅜㅜㅜㅜ
https://ideone.com/LlO3sU
설명좀 해주시면 감사하겠습니다....
경우의 수 나누는 2차원 DP임
문제를 살짝 변형해서 일렬로 늘어져 있으면 어떻게 풀어야할지 생각해볼컷
감사합니다 - dc App
D[n][k] = n개 중에 띄엄띄엄 k개 고르기
D[n][k] = D[n-1][k] + D[n-2][k-1]
위는 그냥 원둘레가 아니라 일직선이라 생각하고 세운 점화식이고
원둘레니까 그냥 구한 D[n][k]에서 여기에 포함된 양쪽 끝을 고른 경우의 수 D[n-4][k-2]를 빼주는거임
그리고 다른사람이 올린 코드는 메모리 아끼기 위해 d[j]를 처음에 D[2j-1][j]=1로 취급해서 1로 초기화 한거임. 그리고 반복문을 i번 돌면 d[j]는 위에서 말한 dp에서 D[2j-1+i][j]의 값을 갖는거임. 그래서 총 반복문을 n-2k+1번 돌리면
d[k]=D[n][k], d[k-2]=D[n-4][k-2]가 되니까 d[k]-d[k-2]가 위에서 구한 값들의 빼기랑 같은거임. 이런 방법은 굳이 따라할 필욘 없다
결론 2차원 dp가 정해이고, 남의 코드는 메모리를 아끼기 위해 뭔가 한거지만 시간복잡도는 똑같다.
만약 메모리를 아낄거면 그냥 배열 선얼할 때 D[5][1001] 선언하고 D[n][k], D[n-1][k], D[n-4][k-2] 등등을 전부 D[n%5][k], D[(n-1)%5][k], D[(n-4)%5][k-2]로 접근하면 됨. 이 방식의 이름을 까먹었는데 이러면 최근에 다룬 n에 대해 D[n~n-4][k] 값을 잃지 않고 쓸 수 있음
와 한시간 동안 친절한 답변......진짜 너무 감사드립니다.............혼자 공부중이라 저런 풀이들 알아볼수가 없었는데 진짜 이해 잘됐습니다 넘 감사드려요