λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
CS/μ•Œκ³ λ¦¬μ¦˜

λ°±μ€€ 1904 파이썬 - 01타일 - 동적 κ³„νšλ²•, ν–‰λ ¬

by πŸŒ»β™š 2021. 10. 8.

λ°±μ€€ 1904 파이썬

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

 

1904번: 01타일

μ§€μ›μ΄μ—κ²Œ 2진 μˆ˜μ—΄μ„ κ°€λ₯΄μ³ μ£ΌκΈ° μœ„ν•΄, 지원이 μ•„λ²„μ§€λŠ” κ·Έμ—κ²Œ 타일듀을 μ„ λ¬Όν•΄μ£Όμ…¨λ‹€. 그리고 이 각각의 타일듀은 0 λ˜λŠ” 1이 μ“°μ—¬ μžˆλŠ” λ‚±μž₯의 타일듀이닀. μ–΄λŠ λ‚  짓ꢂ은 동주가 지원이

www.acmicpc.net

ν•΄λ‹Ή λ¬Έμ œλŠ”... "00" 타일과 "1" νƒ€μΌλ‘œ λ§Œλ“€ 수 μžˆλŠ” μ΄μ§„μˆ˜μ˜ κ°€μ§“μˆ˜λ₯Ό μ°ΎλŠ” λ¬Έμ œμž…λ‹ˆλ‹€. 이 λ¬Έμ œλ„ κ²°κ΅­ 1타일과 00타일을 μ΄μ „μ˜ νƒ€μž…μ— λΆ™μΉ˜λŠ” λ¬Έμ œμ΄λ―€λ‘œ λ©”λͺ¨μ΄μ œμ΄μ…˜μ„ μ΄μš©ν•œ λ™μ κ³„νšλ²•μœΌλ‘œ ν’€ 수 μžˆλ‹€. 그런데... 직접 μ†μœΌλ‘œ 숫자의 νŒ¨ν„΄μ„ κ³„μ‚°ν•΄λ³΄λ‹ˆ ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄κ³Ό μ™„μ Ό λ™μΌν•œ 숫자의 νŒ¨ν„΄μ„ κ°–κ³  μžˆμ—ˆμŠ΅λ‹ˆλ‹€. κ·Έλž˜μ„œ 이 λ¬Έμ œλŠ” ν–‰λ ¬ 멱법을 μ‚¬μš©ν•΄μ„œ ν•΄κ²°ν•  수 μžˆμ—ˆμŠ΅λ‹ˆλ‹€.

 

Python 풀이 1

첫번 μ§Έ ν’€μ΄λŠ” 동적 κ³„νšλ²•μ„ μ‚¬μš©ν–ˆμŠ΅λ‹ˆλ‹€.

import sys
read = sys.stdin.readline

N = int(read())
cache = [0] * (N+2)
cache[1] = 1
cache[2] = 2

for i in range(3, N+1):
    cache[i] = (cache[i-1] + cache[i-2]) % 15746
print(cache[N])
  • 초기 κ°’ 1, 2λ₯Ό μ €μž₯해두고 값을 μž¬μ‚¬μš©ν•˜λ©΄μ„œ 문제λ₯Ό ν’€μ—ˆμŠ΅λ‹ˆλ‹€.

문제λ₯Ό ν’€κΈ°λŠ” ν–ˆλŠ”λ°... λ©”λͺ¨λ¦¬ μ‚¬μš©λŸ‰λ„ λ†’κ³  μˆ˜ν–‰ 속도가 였래 걸리길래.... μ½”λ“œλ₯Ό 쑰금 μˆ˜μ •ν•΄λ΄€μŠ΅λ‹ˆλ‹€.

 

 

Python 풀이 2

import sys
read = sys.stdin.readline

N = int(read())
n1 = 1
n2 = 2
res = 1 if N == 1 else 2

for i in range(3, N+1):
    res = (n1 + n2) % 15746
    n1, n2 = n2, res
print(res)

λ‘λ²ˆ μ§Έ ν’€μ΄λŠ” 동적 κ³„νšλ²•μœΌλ‘œ ν’€μ—ˆμ„ λ•Œ 많이 μž‘μ•„λ¨Ήλ˜ λ©”λͺ¨λ¦¬λ₯Ό 쀄이기 μœ„ν•΄ μΊμ‹œ 리슀트λ₯Ό μ—†μ• κ³  λ³€μˆ˜λ‘œ 계속 λ°”κΏ”κ°€λ©΄μ„œ 풀도둝 μˆ˜μ •ν–ˆμŠ΅λ‹ˆλ‹€. λ©”λͺ¨λ¦¬λŠ” 2배이상 μ ˆμ•½λ˜μ—ˆκ³  μ‹œκ°„λ„ 25% 정도 μ ˆκ°ν•  수 μžˆμ—ˆμŠ΅λ‹ˆλ‹€.

 

 

Python 풀이 3

3번째 ν’€μ΄λŠ” ν–‰λ ¬μ˜ 멱법을 μ‚¬μš©ν–ˆμŠ΅λ‹ˆλ‹€.

import sys
read = sys.stdin.readline

N = int(read())
A = [[1, 1], [1, 0]]

def matrix_mult(A, B):
    temp = [[0] * 2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                temp[i][j] += (A[i][k] * B[k][j])

    for i in range(2):
        for j in range(2):
            temp[i][j] %= 15746
    return temp

def matrix_pow(n, M):
    if n == 1:
        return M
    if n % 2 == 0:
        temp = matrix_pow(n//2, M)
        return matrix_mult(temp, temp)
    else:
        temp = matrix_pow(n-1, M)
        return matrix_mult(temp, M)

print(matrix_pow(N, A)[0][0])

 λ¬Έμ œμ˜ κ²°κ³Όλ₯Ό μ†μœΌλ‘œ 계속 ν’€μ–΄λ³΄λ‹ˆκΉŒ... ν”Όλ³΄λ‚˜μΉ˜μ™€ λ™μΌν•˜κ²Œ μˆ«μžκ°€ μ¦κ°€λ˜κ³  μžˆλŠ” 것을 ν™•μΈν–ˆμŠ΅λ‹ˆλ‹€. ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄μ—μ„œ κ°€μž₯ λΉ λ₯Έ νš¨μœ¨μ„ 얻을 수 μžˆλŠ” 방법인 ν–‰λ ¬μ˜ 멱법을 μ΄μš©ν•œ 방법을 μ„ νƒν–ˆκ³ ... 동적 κ³„νšλ²•μœΌλ‘œ ν’€μ—ˆλ˜ 방법보닀 80%정도 λΉ λ₯΄κ²Œ κ²°κ³Όλ₯Ό 얻을 수 μžˆμ—ˆμŠ΅λ‹ˆλ‹€.

 

ν”Όλ³΄λ‚˜μΉ˜λ₯Ό ν–‰λ ¬λ‘œ ν‘ΈλŠ” 방법은 μ•„λž˜ 링크λ₯Ό 톡해 μžμ„Έν•œ λ‚΄μš©μ„ 확인할 수 μžˆμŠ΅λ‹ˆλ‹€.

[CS/μ•Œκ³ λ¦¬μ¦˜] - ν”Όλ³΄λ‚˜μΉ˜ 파이썬으둜 κ΅¬ν•˜λŠ” 3가지 μ•Œκ³ λ¦¬μ¦˜

 

 

λŒ“κΈ€