greentea31's Note

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

풀이 과정

D[n][k] => 마지막이 k로 끝나는 n자리 계단수의 개수라고 하자

모든 인접한 자리의 차이가 1이어야 한다는 점을 고려하면 다음과 같은 점화식을 생각할 수 있다

D[n][0] = D[n-1][1]

D[n][k] = D[n-1][k-1] + D[n-1][k+1] (1 <= k <= 8)

D[n][9] = D[n-1][8]

이를 통해 문제를 해결할 수 있다

소스 코드

N = int(input())
d = [0, [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

for i in range(2, N+1):
    d.append([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
    d[i][0] = d[i-1][1] % 1000000000
    d[i][9] = d[i-1][8] % 1000000000
    for k in range(1, 9):
        d[i][k] = d[i-1][k-1]+ d[i-1][k+1]
        d[i][k] %= 1000000000

print(sum(d[N]) % 1000000000)

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

풀이 과정

https://greentea31.tistory.com/28

위의 문제에서 같은 수를 2번 연속으로 사용하면 안된다는 조건만 추가되었다.

D[n][k] => 정수 n을 마지막이 k로 끝나게끔 합으로 나타내는 경우의 수라고 하자.

그렇다면 k에 따라 점화식을 달리 해서 같은 수가 2번 연속으로 나타나지 않도록 조정이 가능하다.

D[n][1] = D[n-1][2] + D[n-1][3]

D[n][2] = D[n-2][1] + D[n-2][3]

D[n][3] + D[n-3][1] + D[n-3][2]

소스 코드

import sys

T = int(sys.stdin.readline())
d = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 1, 1, 1]]
for i in range(4, 100001):
    d.append([0, (d[i-1][2] + d[i-1][3]) % 1000000009, (d[i-2][1] + d[i-2][3]) % 1000000009, (d[i-3][1] + d[i-3][2]) % 1000000009])
for _ in range(T):
    n = int(sys.stdin.readline())
    print(sum(d[n]) % 1000000009)

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

풀이 과정

https://greentea31.tistory.com/29

위의 문제의 점화식에서 max만 min으로 바꿔주면 되는 문제이다

D[n]을 n개의 카드를 주어진 카드팩을 통해 가장 싸게 구매할 때 지불해야 할 가격이라고 하자.

D[n] = min(D[n-k] + P[k]) (1 <= k <= n)

위의 점화식을 통해 문제를 해결하되, 리스트의 초기값을 큰 수로 잡아놔야 원하는 결과를 얻을 수 있음을 고려해야 한다.

소스 코드

import sys

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
d = [0]
P.insert(0, 0)

for i in range(1, N+1):
    minValue = 10000001
    for j in range(1, i+1):
        minValue = min(minValue, d[i-j] + P[j])
    d.append(minValue)

print(d[N])

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

풀이 과정

D[n]을 n개의 카드를 주어진 카드팩으로 가장 비싸게 살 때의 지불해야 하는 가격이라고 하자.

D[n] = max(D[n-1] + P[1], D[n-2] + P[2], D[n-3] + p[3] ...)

D[n] = max(D[n-k] + P[k]) (1 <= k <= n) 이라는 점화식이 성립한다.

소스 코드

import sys

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
d = [0]
P.insert(0, 0)

for i in range(1, N+1):
    maxValue = 0
    for j in range(1, i+1):
        maxValue = max(maxValue, d[i-j] + P[j])
    d.append(maxValue)

print(d[N])

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

풀이 과정

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 d[n]이라고 하자

n-3을 나타내는 1, 2, 3의 합으로 이루어진 식에 +3을 해주면 정수 n을 나타내고,

n-2을 나타내는 1, 2, 3의 합으로 이루어진 식에 +2을 해주면 정수 n을 나타내고,

n-1을 나타내는 1, 2, 3의 합으로 이루어진 식에 +1을 해주면 정수 n을 나타낸다

따라서, d[n] = d[n-3] + d[n-2] + d[n-1]이라는 점화식이 성립한다 

소스 코드

import sys
T = int(sys.stdin.readline())

for _ in range(T):
    n = int(input())
    d = [0, 1, 2, 4]
    for i in range(4, n+1):
        d.append(d[i-1] + d[i-2] + d[i-3])
    print(d[n])

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

풀이 과정

2xn 모양의 타일이 있으면 2x1 타일을 하나 더 붙여서 2x(n+1) 타일을 만들 수 있고

1x2 타일을 2개 붙이거나, 2x2 타일을 붙여서 2x(n+2) 타일을 만들 수 있다

따라서 d[n] = d[n-1] + 2d[n-2] 라는 점화식이 성립하고, 이를 통해 문제를 해결할 수 있다

소스 코드

d = [0, 1, 3]

n = int(input())
for i in range(3, n+1):
    d.append(2*d[i-2] + d[i-1])
print(d[n] % 10007)

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

풀이 과정

2xn 크기의 타일은 2x(n-1) 크기의 타일에서 1x2 블럭을 하나 붙이거나, 2x(n-2) 크기의 타일에서 2x1 크기의 블럭을 2개 붙이는 방법으로 만들 수 있다. 따라서 2xn 크기의 타일을 만드는 경우의 수의 개수를 D[N]이라고 하면

D[N] = D[N-1] + D[N-2]라는 점화식이 성립한다.

소스 코드

d = [1, 1]

n = int(input())
for i in range(2, n+1):
    d.append(d[i-2] + d[i-1])
print(d[n] % 10007)

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

풀이 과정

3으로 나누어 보고 안되면 2로 나누고, 안되면 1을 빼보고 하는 그리디 방식이 문제를 보자마자 떠오르겠지만, 그리디 방식으로 풀면 답이 나오지 않는 예제를 힌트에서 주었다

D[N]을 숫자 N을 1로 만들기 위해 필요한 연산의 최소 수라고 하자. 그러면 아래와 같은 점화식이 성립한다

1. N이 2와 3으로 모두 나누어 떨어진다면

    D[N] = min(D[N/3], D[N/2], D[N-1]) + 1

2. N이 3으로만 나누어 떨어진다면

    D[N] = min(D[N/3], D[N-1]) + 1

3. N이 2로만 나누어 떨어진다면

    D[N] = min(D[N/2], D[N-1]) + 1

4. N이 2와 3으로 나누어 떨어지지 않는다면

    D[N] = D[N-1] + 1

점화식을 코드로 구현해 문제를 해결할 수 있다.

소스 코드

d = [0] * 1000001
N = int(input())

for i in range(2, N+1):
    d[i] = d[i-1] + 1
    if i % 3 == 0:
        tem = d[i//3] + 1
        if tem < d[i]:
            d[i] = tem
    if i % 2 == 0:
        tem = d[i//2] + 1
        if tem < d[i]:
            d[i] = tem

print(d[N])

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

풀이 과정

https://greentea31.tistory.com/15

위의 문제와 유사하게 해결할 수 있다. 100만 이하의 수에 대해 에라토스테네스의 체로 모든 소수를 찾은 다음 입력 수 - 찾은 소수 == 소수 이면 골드바흐 파티션 변수를 1 늘려주는 식으로 해결할 수 있다. 

위는 N이 12일때 골드바흐 파티션의 개수를 구하는 예시이다.

소스 코드

import sys

prime = []
check = [0] * 1000001
check[0] = 1
check[1] = 1

for i in range(2, 1000001):
    if check[i] == 0:
        prime.append(i)
        for j in range(2*i, 1000001, i):
            check[j] = 1

T = int(sys.stdin.readline())

for _ in range(T):
    count = 0
    N = int(sys.stdin.readline())
    for i in prime:
        if i >= N:
            break
        if not check[N - i] and i <= N-i:  # 순서만 다른거 counting 하지 않기 위해
            count += 1
    print(count)

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

풀이 과정

10진수 13을 2진수로 바꾸는 방법이 위와 같듯, 어떤 수를 -2진수로 바꾸려면 동일한 과정을 진행해주면 된다 예시를 보자.

단, 언어마다 음수로 나눴을때의 나머지가 나오는 경우가 다를 수 있으므로, 위의 그림과 같은 나머지가 나오도록 적절히 조정해주어야 한다.

파이썬에서는 나누어지는 수가 음수인지 양수인지에 따라 결과를 달리 해줘야 한다.

소스 코드

def divide(n, ans):
    if n == 0:
        ans.append(0)
        return
    if n == 1:
        ans.append(1)
        return
    if n % 2 == 0:
        ans.append(0)
        divide(n // -2, ans)
    elif n < 0:
        ans.append(1)
        divide((n // -2) + 1, ans)
    else:
        ans.append(1)
        divide((n // -2) + 1, ans)


N = int(input())
answer = []
divide(N, answer)
answer.reverse()
print(f'{"".join(str(i) for i in answer)}')