팰린드롬

    [Java] 백준 1509 (팰린드롬 분할) Gold 1
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1509 (팰린드롬 분할) Gold 1

    Problem : 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 Approach 주어진 문자열이 최소 몇 개의 팰린드롬 문자열로 구성되어 있는지를 구하는 문제이다. 팰린드롬 문자열 자체를 구하는 로직은 O(n^2) 의 시간복잡도를 가진다. 팰린드롬 문자열을 구하는 방법은 투포인터를 사용하였다. DP[i] 는 0 ~ i인덱스의 문자열이 몇 개의 최소 팰린드롬 문자열로 구성되는지..

    [java] 백준 10942 (팰린드롬) Gold 2
    Algorithm/Baekjoon Online Judge

    [java] 백준 10942 (팰린드롬) Gold 2

    Problem : https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net Approach 팰린드롬은 주어진 문자열을 거꾸로해도 원래의 문자열과 같은 경우를 말한다. 일반적으로 팰린드롬은 DP 문제가 아니지만, 하나의 문자열으로 범위를 나누어 팰린드롬인지를 검사할 때에는 DP를 써서 상태를 저장한다면 시간을 조금 단축시킬 수 있다. 일단 범위 (s, e) 가 팰린드롬이라면, 시작인덱스와 끝인덱스에 같은 수를 더하고 뺀 범위는 항상 팰린드롬이다. 예를 들어, (s, e) 가 팰린드롬이면, (s..

티스토리툴바