greentea31's Note

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)}')

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

풀이 과정

1. 파이썬 내장 함수로 문자열 입력을 8진수로 변환한 뒤, 다시 2진수로 바꿔주는 방법

2. 8진수를 케이스 분류해서 2진수로 바꿔주는 방법

소스 코드

a = input()
a = int(a, 8)
print(bin(a)[2:])

a = input()
b = []
for i in a:
    if i == '7':
        b.append('111')
    elif i == '6':
        b.append('110')
    elif i == '5':
        b.append('101')
    elif i == '4':
        b.append('100')
    elif i == '3':
        b.append('011')
    elif i == '2':
        b.append('010')
    elif i == '1':
        b.append('001')
    elif i == '0':
        b.append('000')

answer = list(''.join(b))
while answer and answer[0] == '0':
    answer.pop(0)
if answer:
    print(''.join(answer))
else:
    print(0)

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

풀이 과정

파이썬에는 진법을 편리하게 다루기 위한 내장 함수가 마련되어있다.

int(string, base) => string 문자열을 base진법의 정수로 바꾸어줌

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

소스 코드

N = int(input(), 2)
print(oct(N)[2:])