algoshipda의 블로그

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

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

문제 : https://www.acmicpc.net/problem/1727 더 쉬운 문제로 남녀 모두 $k$명이 있는 문제를 생각해보자. 이 경우는 두 집합을 각각 정렬한 뒤 그 순서에 맞게 매칭을 시키면 최적이 된다. 본 문제는 남자 $n$명, 여자 $m$명 $($$n >= m$ 이라 가정$)$이라 할때, 매칭될 남자 $m$명을 고르는 문제로 생각할 수 있다. 남녀 집합을 모두 정렬하고 테이블을 아래와 같이 정의하자. $D[i][j]$ : 남자 $i$번, 여자 $j$번까지 매칭($j$쌍 커플) 했을 때 최소 성격 차이의 합. 상태전이는 LCS와 비슷하게 시켜주면 된다. 코드 : http://ideone.com/ehzO4C