2018. 09. 01 백준 알고리즘 파이썬 정리

2133 - 타일채우기

소스코드

import sys

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

D = [0 for i in range(num+1)]

D[1] = 0

if num >= 2:
    D[2] = 3

for i in range(3, num+1):
    D[i] = 3*D[i-2]
    for j in range(i-4, 0, -2):
        D[i] += 2*D[j]
    if i % 2 == 0:
        D[i] += 2

sys.stdout.write(str(D[num]))

코멘트

2n때랑 다르게 아래에 한칸이 더 생겨버렸으므로 더 생각을 해야만 했던 문제. 결국엔 초반 패턴을 직접 그려서 경우의 수를 구한 다음에, 그 이후에 나오는 것들은 다이나믹 프로그래밍으로 구하는 형식이었다. 결국 초기 값은 직접 파악해야한다는 점이 마음에 들지 않는다. 달리 뾰족한 수도 없겠지만...

2225 - 합분해

소스코드

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())

P = [[1 if i>0 else 0 for i in range(k + 1)] for j in range(n + 1)]

for i in range(1, n+1):
    for j in range(1, k+1):
        P[i][j] = P[i-1][j] + P[i][j-1]

sys.stdout.write(str(P[n][k] % 1000000000))

코멘트

소스코드를 오랜만에 읽으니 잘 파악이 안 된다. 다이나믹 프로그래밍은 직접 손으로 표를 그려야 제대로 파악하기가 쉽다. (i-1, j의 P에 +1을 하는 가짓수) + (i, j-1의 P에 +0을 하는 가짓수)가 P[i][j]이다.

2011 - 암호 코드

소스코드

#Q : 2011

import sys


line = sys.stdin.readline().strip()

D = [[0, 0] for i in range(len(line) + 1)]

D[1] = [1, 0]

if line == '0':
    sys.stdout.write('0')
    exit()

for i in range(2, len(line)+1):
    if line[i-1] == '0':
        D[i][0] = 0
    else:
        D[i][0] = sum(D[i-1])
    if (line[i-2] >= '3') or (line[i-2] == '2' and line[i-1] > '6') or (line[i-2] == '0'):
        D[i][1] = 0
    else:
        D[i][1] = D[i-1][0]

sys.stdout.write(str(sum(D[len(line)]) % 1000000))

코멘트

앞의 수가 어떤 게 오느냐에 따라서 해석할 수 있는 가짓수가 달라진다. 와인 마시기 문제나 계단 문제와 비슷하게 경우의 수를 두가지로 둬야한다. 현재 i번째의 수가 앞의 수와 이어지는 두자리 수일지, 아니면 별개의 한가지 수인지를 계산한다.