acmicpc.net 1254(DP, 팰린드롬), 1695,5502(DP, 팰린드롬), 11203(이진 트리)

https://www.acmicpc.net/problem/1254

http://qkqhxla1.tistory.com/738의 10942번 문제의 dp테이블이 해당 범위에서 팰린드롬인지

판단하는 함수이다.

1. 팰린드롬인지 판단해놓는다. 끝에 x개의 문자를 덧붙이는것이므로 i~끝까지의 팰린드롬이 가장 긴

범위를 찾는다. i가 2라서 2~끝까지 팰린드롬이다. 그러면 앞의 0,1은 팰린드롬이 아니라는 소리이므로

0,1번 인덱스 문자 두개만 붙여주면 된다 즉 길이 + 2가 답이다 이경우엔. 이런식으로 품

# -*- encoding: utf-8 -*-
s=raw_input()
dp = [[0 for i in xrange(1002)] for j in xrange(1002)]
for i in xrange(len(s)-1,-1,-1):
    for j in xrange(i,len(s)):
        if i==j: dp[i][j] = 1
        elif j-1==i and s[i]==s[j]: dp[i][j] = 1
        elif dp[i+1][j-1]==1 and s[i]==s[j]: dp[i][j] = 1

index = 0
for i in xrange(len(s)):
    if dp[i][len(s)-1]==1:
        index = i
        break
#for i in xrange(4):
#    for j in xrange(4):
#        print dp[i][j],
#    print

print len(s) + index

https://www.acmicpc.net/problem/1695, https://www.acmicpc.net/problem/5502

똑같다. 근데 파이썬으로는 시간초과만 떴다. 채점현황보니 파이썬으로 맞은 사람이 한명도 없는걸로봐서

파이썬으로는 못 푸는거같다. C++로 바꿨더니 통과했다.

#include <iostream>
#include <cstdio>
using namespace std;
  
int n,dp[5002][5002], arr[5002];
  
int f(int l, int r)
{
    if(l>=r) 
        return 0;
    int& ret = dp[l][r];
    if(ret!=0) return ret;
  
    if(arr[l]==arr[r]) //같으면 안으로 더 들어가기.
    {
        ret = f(l+1, r-1);
        return ret;
    }
    ret = 1 + min(f(l,r-1), f(l+1,r)); //다르면 문자 한개 삽입 후 l~r-1, l+1~r 범위중 작은 값.
    return ret;
}
  
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);
    printf("%d\n",f(0,n-1));
    return 0;
}

https://www.acmicpc.net/problem/11203

잘 계산한다.

# -*- encoding: utf-8 -*-
s=raw_input().split()
if len(s)==1:
    print 2**(int(s[0])+1)-1
else:
    h,lr=s
    root = 0
    for i in xrange(len(lr)):
        if lr[i]=='L':
            root = root*2 + 1
        else:
            root = root*2 + 2
    print 2**(int(h)+1)-1 - root