멍청하게 이항계수 합으로 접근하다가 설마 DP인가? 라고 생각했을 때 남은 시간 15분....
[일반] D번 풀이 생각났는데 ㅜㅜ
ㅅㅅ(1.240)
2019-02-19 02:48
추천 0
댓글 6
다른 게시글
-
ㅅㅂ 왜이리 어려움 [1][일반] 익명(223.39) | 19.02.19추천 0
-
[공지] 대회 진행 중에 대회와 관련된 글을 올리지 말아주세요 [3][일반] 시아닌(kimjg1119) | 19.02.19추천 0
-
프로그래머스 '도둑질' 문제 아이디어좀.. [3][일반] ㅁㄴㅇ(211.59) | 19.02.18추천 0
-
2주째 안풀리는문제잇으면 그냥 답보는게 나음? [11][일반] 닝겐(rkddhrwk) | 19.02.18추천 0
-
TSP DP가 빨라 분기한정법이 빨라? [1][일반] 익명(210.105) | 19.02.18추천 0
-
백준강의 중급2까지 다들었다[일반] 익명(118.221) | 19.02.18추천 0
-
A 1분만에 푸는 건 뭐야? [4][일반] 익명(218.54) | 19.02.18추천 0
-
삼성 알고리즘 기출 푸는 데 필요한 기초 어떻게 공부할까요 [1][질문] 익명(221.153) | 19.02.17추천 0
-
어떤 배열 구간을 전부 같은수로 빼는/더하는 테크닉 [9][질문] ㅁㄴㅇ(1.216) | 19.02.17추천 0
-
오늘 구슬탈출 , 2048 문제 풀었는데 니들은 이런거 처음부터 풀었겠지 [3][일반] 익명(222.112) | 19.02.17추천 0
풀이 뭐에요?? 저도 이항계수생각하다가 전혀아니겠다싶어서 던졌는데...
처음에는 1로 다 채워진 배열을 점점 m개씩 묶어서 그걸 0으로 만드는 식으로 생각해보셈
dp[i] = 처음 i개에 대한 경우의 수 dp[i] = sum(dp[i-m..i-1])이라는 간단한 점화식이 나오는데
이걸 행렬 곱으로 빠르게 계산 할 수 있음
행렬제곱 DP는 종만북 보면 나옴
오오 저는 어차피 못 풀 문제였네요 종만북 보러가겠읍니다