[python] 백준 1509 팰린드롬 분할
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 해결 팰린드롬은 좌우 대칭인 문자열을 의미한다 문자를 하나씩 나누면 무조건 팰린드롬 분할이 된다. 두 개씩 보면서 팰린드롬을 확인하는 것도 어렵지 않다. $O(N)$ 3개 이상일 때는 어떻게 할 수 있을지 어려웠다. 길이를 3부터 L까지 늘려나가면서 $l$ 확인한다. 시작점을 0부터 $L-l$까지 이동하며 잡고 끝점을 시작점..
2024. 2. 25.
[python] 백준 11055 가장 큰 증가 부분 수열
https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 해결 전통적인 dp문제 dp[n]을 n을 마지막으로 포함하는 부분 증가 수열중 합이 가장 큰 수를 나타낸다고 하자. 이 때 들어가는 수열중 n 이전 마지막 수를 i라 할 때 dp[n] = max(dp[i]+A[n], dp[n])이 될 것이다. 따라서 이 것을 생각하고 풀면 끝 CODE import sys input = sys.stdi..
2022. 12. 29.