acmicpc.net 1427, 1463번(DP), 1520번(DP)

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

print ''.join(sorted(raw_input(),reverse=True))

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

동적 계획법 문제.

c 코드로 짤 경우 재귀로도 된다. http://blog.naver.com/swyu23/220757146631 처음에 요 분의 블로그와 비슷하게 짰는데 c로는 통과가 되는데 동일한 코드를 파이썬으로 바꿨을때 통과가 안 됬다. 그래서 아예 로직을 재귀를 안쓰도록 바꿨다.

n = int(raw_input())
n_list = [-1 for i in range(1000001)]
n_list[1] = 0
n_list[2] = 1
n_list[3] = 1
c = 4
while c <= n:
    v = 999999
    if c%3==0:
        t = n_list[c/3]
        if v > t:
            v = t
    if c%2==0:
        t = n_list[c/2]
        if v > t:
            v = t
    t = n_list[c-1]
    if v > t:
        v = t
    n_list[c] = v + 1
    c += 1
print n_list[c-1]

재귀적으로 짠 파이썬 코드. 

import sys
sys.setrecursionlimit(100000) #요걸로 재귀를 더할수있게 조절할수 있지만 일정 이상 되면 프로그램이 그냥 죽어버린다.
n_list = [-1 for i in range(1000001)]
def check(n):
    if n_list[n]!=-1:
        return n_list[n]

    v = 999999
    if n%3==0:
        t = check(n/3)
        if v > t:
            v = t

    if n%2==0:
        t = check(n/2)
        if v > t:
            v = t

    t = check(n-1)
    if v > t:
        v = t

    n_list[n] = v + 1
    return n_list[n]

n = int(raw_input())
n_list[1] = 0
print check(n)

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

def find_way(m,i,j,M,N):
    if i>M-1 or i<0 or j>N-1 or j<0:
        return 0
    if dp_maps[i][j] != 0:
        return dp_maps[i][j]
    if j-1>=0 and m[i][j] < m[i][j-1]: dp_maps[i][j] += find_way(m,i,j-1,M,N)
    if j+1<=N-1 and m[i][j] < m[i][j+1]: dp_maps[i][j] += find_way(m,i,j+1,M,N)
    if i-1>=0 and m[i][j] < m[i-1][j]: dp_maps[i][j] += find_way(m,i-1,j,M,N)
    if i+1<=M-1 and m[i][j] < m[i+1][j]: dp_maps[i][j] += find_way(m,i+1,j,M,N)
    return dp_maps[i][j]

m,n = map(int,raw_input().split())
maps = [map(int,raw_input().split()) for i in range(m)]
dp_maps = [[0 for j in range(n)] for i in range(m)]
dp_maps[0][0]=1
print find_way(maps,m-1,n-1,m,n)