컴공과고씨

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이런 문제의 경우 각 경우 마다 최적의 경우의 수를 선택하면서 가면 된다. 저런식으로 각 자리를 늘려가면서 A에서 C가 들어갔을 때 LCS의 경우 0 AC와 C의 LCS = 1 이런식으로 표를 채워가준다. 중요한 것은 LCS가 하나 더 늘어나는 경우는 문자가 들어갈 수 있을 때 예를 들면 ACAYK 와 CAP 다음 순서에 ACAYKP 와 CAP가 나온다..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 처음에 고민을 하다가 팩토리얼 숫자를 그리면서 규칙을 좀 살펴보니 5배수가 곱해질때마다 뒤에 0 이 붙는 것을 보고 이것을 이용해 풀었다. 왜냐하면 10이 곱해지려면 2와 5가 필요한데 2는 항상 5보다 많기 때문에 5가 몇개 있는지 세주면 된다. 주의 해야할 것은 5의 배수중 25 와 같이 5가 2번 곱해진것은 0이 2개가 추가 됨에 주의 해주면된다. 위 방법과 다이나믹 프로그래밍을 이용하여 하나씩 0의 개수를 저장하는데 5배수가 들어있는 수가 곱해지는 차례에는 i-5번..