TILING 문제. SinAska 안녕하세요. 열심히 알고리즘에 정진중인 알고리즘 비기너 입니다. TILING문제를 보고 아래와 같이 점화식을 유도했습니다. T[n] = T[n-1] + 2*T[n-2] + 5*T[n-3] 다만 N이 매우 큰 10^9라 1억개나되는 결과값을 모두 저장하기에는 다소 어려워보여 T의 최대크기를 3으로 하고 슬라이딩 윈도우 기법을 적용하였는데, 테스트 케이스 3000개정도에 대해 2초정도의 시간제한이 걸려있네요. 점화식, 슬라이딩윈도우 기법까지 생각해보았는데, 한층더 진보된 접근 방식이 필요해보입니다. 풀이좀 부탁드립니다. 8년 전
3개의 댓글이 있습니다. skylife927 비기너가 아니신듯.. 다음주에 풀어보고 댓글 달도록 하겠습니다. ㅎ 프로필사진이 인상적이네요. 8년 전 link hyunhwan 힌트를 드리자면 이 링크의 내용을 이용하여 O(logN)에 해법을 구할 수 있습니다. 8년 전 link SinAska 감사합니다. 큰 도움이 되었네요.! 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
SinAska
안녕하세요. 열심히 알고리즘에 정진중인 알고리즘 비기너 입니다.
TILING문제를 보고 아래와 같이 점화식을 유도했습니다.
T[n] = T[n-1] + 2*T[n-2] + 5*T[n-3]
다만 N이 매우 큰 10^9라 1억개나되는 결과값을 모두 저장하기에는
다소 어려워보여
T의 최대크기를 3으로 하고 슬라이딩 윈도우 기법을 적용하였는데,
테스트 케이스 3000개정도에 대해
2초정도의 시간제한이 걸려있네요.
점화식, 슬라이딩윈도우 기법까지 생각해보았는데,
한층더 진보된 접근 방식이 필요해보입니다.
풀이좀 부탁드립니다.
8년 전