우주의 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/14391

n, m = map(int, input().rstrip().split())
a = [list(map(int, input())) for _ in range(n)]
ans = 0
for s in range(1 << (n * m)): # n * m 사이즈의 비트마스크
    sum = 0
    for i in range(n):
        cur = 0
        for j in range(m):
            k = i * m + j # row major order
            if (s & (1 << k)) == 0: # 가로일 경우
                cur = cur * 10 + a[i][j]
            else:
                sum += cur
                cur = 0
        sum += cur
    for j in range(m):
        cur = 0
        for i in range(n):
            k = i * m + j
            if (s & (1 << k)) != 0: # 세로일 경우
                cur = cur * 10 + a[i][j]
            else:
                sum += cur
                cur = 0
        sum += cur
    ans = max(ans, sum)
print(ans)

- 가로 조각과 세로 조각 두가지로 나뉨
- o과 1로 나누어진 NM개의 칸으로 생각 (max 16개)
- 4X4 공간을 1차원으로 이어붙여 생각 (max 16칸, 16자리 비트로 표현)

1. 비트마스크를 이용해 모든 경우를 구하고
2. 수의 합을 구해주면 된다

-A[I][J] -> i*m+j (row major order)

비트 마스크에 대해 오늘 공부하기 시작했는데,

문제에서는 뭐 배열의 최대 값을 구하라는데 2^n -1 을 왜 차곡차곡넣고있지? 라고 생각했었다.

비트 값으로 연산을 하자는게 아니라

비트를 통해 현재 상태를? 구분짓자는 내용이라는걸 깨달은 순간 문제가 보이기 시작했다.

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을 사용할 수 있다면 사용하는게 가장 빠른 시간을 얻을 수 있는 것 같다.

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

"""
a - > b
1. 곱하기 2
2. 1을 수의 가장 오른쪽에 추가

"""
a, b = map(int, input().split())
count = 1

def go(a, b, count):
    if a == b:
        print(count)
        exit()
    if a > b:
        return
    go(a * 2, b, count + 1)
    go(int(str(a) + "1"), b, count + 1)


go(a, b, count)
print(-1)

재귀 함수를 이용하여 푼 문제

재귀의 조건을 살펴보자

1. A와 B가 같은 값이면 재귀 종료

2. A가 B보다 커지면 재귀 종료

3. 1-2에 해당하지 않는 경우 매 순간 a에 대해 곱하기 2, 1을 추가 해주면 됨