우주의 IT 소행성

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

MOD = 1000000000
n, k = map(int, input().split())
d = [[0] * (n + 1) for _ in range(k + 1)]
d[0][0] = 1
for i in range(1, k + 1):
    for j in range(0, n + 1):
        for l in range(0, j + 1):
            d[i][j] += d[i - 1][j - l]
        d[i][j] %= MOD
print(d[k][n])

x + x + x + ... + L = N
일 때, L 이전까지의 수열들
합 = N - L개
개수 = K - 1개
이므로, D[K][N] = D[K - 1][N - L]이 된다.

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

"""
1. 수를 변경할 수는 없음
2. 주어진 수의 순서를 변경해 최대 차이를 만들기
방법의 수 : N!, 최대 8, 40320 가지 수

"""
def next_permutation(a):
    i = len(a) - 1
    while i > 0 and a[i - 1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a) - 1
    while a[j] <= a[i - 1]:
        j -= 1

    a[i - 1], a[j] = a[j], a[i - 1]
    j = len(a) - 1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

def calc(a):
    ans = 0
    for i in range(1, len(a)):
        ans += abs(a[i] - a[i - 1])
    return ans
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
while True:
    temp = calc(a)
    ans = max(ans, temp)
    if not next_permutation(a):
        break
print(ans)

재귀를 이용한 방법

from itertools import permutations
n = int(input())
data = list(map(int, input().split()))
ans = 0

for a in permutations(data, n):
    tmp = 0
    for i in range(1, len(a)):
        tmp += abs(a[i] - a[i - 1])
    ans = max(tmp, ans)
print(ans)

itertools의 permutations를 이용한 방법

STL을 사용할 수 있다면 사용하는게 가장 빠른 시간을 얻을 수 있는 것 같다.

from collections import deque

def bfs(s, t):
    queue = deque()
    queue.append((s, t, 0))
    visited = [-1] * (200)

    while queue:
        s, t, count = queue.popleft()
        if s <= t and visited[s] == -1:
            queue.append((s * 2, t + 3, count + 1))
            queue.append((s + 1, t, count + 1))
            if s == t:
                return count


c = int(input())
for i in range(c):
    s, t = map(int, input().split())
    print(bfs(s, t))

bfs를 통해 풀 수 있는 문제.
매 분기마다 A의 발차기를 할지, B의 발차기를 할지
모든 분기를 저장하여 가장 빠른 s == t에 도달한 count를 출력하면 끝.