Dynamic Programming Optimizations

http://codeforces.com/blog/entry/8219

댓글

댓글 쓰기

이 블로그의 인기 게시물

BOJ 2401 - 최대 문자열 붙여넣기

문제 :  https://www.acmicpc.net/problem/2401 각각의 짧은 문자열들이 긴 문자열에서 어디에 등장하는지만 알 수 있다면, 이 문제는 전형적인 다이나믹 프로그래밍 문제가 된다. 그러니깐 KMP를 돌리면서 테이블을 채우면 된다. 시간 복잡도는 긴 문자열 길이 $S$, 짧은 문자열 길이 $T$, 짧은 문자열의 수 $N$이라 할때 $O(N * (S + T))$가 된다. 코드 :  http://ideone.com/zloOUb
계속 읽기

BOJ 1034 - 램프

문제 :  https://www.acmicpc.net/problem/1034 램프에 $K$번의 조작을 다 하고 나서 최종적으로 몇 개의 행의 불이 완전히 켜져있다고 생각해보자. 불이 완전히 켜져있는 행들은 초기에 서로 켜져있는 불의 상태가 완전히 같았어야한다. 왜냐하면 램프에 가해지는 조작은 열 단위로 가해지기 때문이다.  위 사실을 알고나면, 문제를 이렇게 생각할 수 있다. $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는가? 만약에 켤 수 있다면 그 행과 똑같이 생긴 행의 수를 답으로 고려해 볼 수 있고, 최종 답은 그러한 행의 수 중 최대가 된다. 이제 $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는지를 알 수 있으면 되는데, 이는 처음에 꺼져있는 열의 수보다 $K$가 크거나 같을 때 홀짝만 잘 따지면 알 수 있다. 코드 :  http://ideone.com/tcrFIU
계속 읽기