greentea31's Note

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:])

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

풀이 과정

동생이 있는곳을 지나치지 않고 방문하려면 움직이는 칸수가 동생과의 거리의 약수여야 한다

=> 모든 동생을 찾기 위한 공통적인 약수의 최대값을 구해야 한다

=> 동생과의 거리의 최대공약수를 구해달라는 말이다

GCD(a, b, c) = GCD(GCD(a, b), c)가 성립한다. 3개 이상의 수의 최대공약수를 구할때는 앞에서부터 2개씩 묶어서 구해주면 된다

소스 코드

import sys


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


N, S = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))

for i in range(N):
    A[i] = abs(S - A[i])
answer = A[0]
for i in range(1, N):
    answer = gcd(answer, A[i])

print(answer)

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

풀이 과정

문제에서 시킨대로 주어진 입력의 모든 쌍을 구해 각 쌍의 GCD를 더해주면 된다

10, 20, 30, 40이 입력으로 들어왔다면 (10, 20), (10, 30), (10, 40), (20, 30), (20, 40), (30, 40)이 입력의 모든 쌍일 것이고 각 쌍의 GCD는 10, 10, 10, 10, 20, 10일테니 답은 70이 나올 것이다.

소스 코드

import sys


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)


t = int(sys.stdin.readline())
for _ in range(t):
    n = list(map(int, sys.stdin.readline().split()))
    sumNumber = 0
    for i in range(1, n[0] + 1):
        for j in range(i+1, n[0] + 1):
            sumNumber += gcd(n[i], n[j])
    print(sumNumber)

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

풀이 과정

N!에서는 2가 인수로 들어가는 횟수보다 5가 인수로 들어가는 횟수가 항상 더 적었는데 조합에서는 그렇지 않다.

7C3의 경우 2가 인수로 들어가는 횟수는 0번이고 5가 인수로 들어가는 횟수가 1번임을 알 수 있다.

따라서 이번에는 nCk에서 2가 인수로 들어가는 횟수, 5가 인수로 들어가는 횟수를 일일이 세주어야 한다.

이므로 number_count(n, k)라는 함수가 n!에서 a가 인수로 몇번 들어가는지 결과값을 반환해준다고 하면

number_count(n, a) - number_count(n-k, a) - number_count(k, a)가 성립한다

n!에서 a가 인수로 몇번 들어가는지 결과값을 반환하는 함수를 파이썬 코드로 짜면

def number_count(n, k):
    count = 0
    while n != 0:
        n = n // k
        count += n
    return count

이므로 이를 활용해서 문제를 해결할 수 있다

소스 코드

def number_count(n, k):
    count = 0
    while n != 0:
        n = n // k
        count += n
    return count


n, m = map(int, input().split())
count2 = number_count(n, 2) - number_count(n-m, 2) - number_count(m, 2)
count5 = number_count(n, 5) - number_count(n-m, 5) - number_count(m, 5)

print(min(count2, count5))