[백준] 11576, 1463, 11726, 11727, 9095 (파이썬)

오늘의 알고리즘 풀이는 다이나믹 프로그래밍에 중점을 두었다. 상향식으로 제일 작은 인덱스부터 목표값까지 나올 수 있는 경우의 수를 다 구하는 방식, 점화식을 이용하여 규칙성을 찾는 방식을 통해서 문제를 풀어나갔다. 경우의 수를 찾는 과정에서 실수를 하여 틀리는 경우가 종종 있었기에 이 부분을 유의하면 될 것 같다. 규칙성을 찾는 것은 경험이 쌓일수록 편해지는 느낌. 이에 대한 연습을 이어나가도록 해야겠다.

백준 11576번 Base Conversion

import sys
# A진법의 수를 m자리만큼 입력받아 B진법의 수로 표현
jin_a, jin_b = map(int,sys.stdin.readline().split())
m = int(sys.stdin.readline())
a_num = list(map(int,sys.stdin.readline().split()))
ten = 0
count = 0
for i in a_num[::-1]:
    ten += i*(jin_a**count)
    count +=1
ten_b_list = list()
while ten>0: 
    ten_b_list.append(str(ten % jin_b)) 
    ten //= jin_b
print(*ten_b_list[::-1])

백준 1463번 1로 만들기

# 오늘 가장 오래 막혔던 문제
# 다이나믹 프로그래밍, 일반적인 방법으로 접근하면 안된다.
# 상향식 : 제일 작은 인덱스부터 목표값으로
# 하향식 : 맨 위의 값부터 재귀로 제일 작은 인덱스로
import sys
x = int(sys.stdin.readline())
d = [0] * (x + 1) # [0] x+1개 만듬
for i in range(2, x + 1): # 2부터 x까지
    d[i] = d[i - 1] + 1 # i =  앞의 수 + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1) # 3으로 나눈수+1 과 앞의 수+1 비교
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1) # 2로 나눈수+1 과 앞의 수+1 비교
print(d[x])

백준 11726번 2×n 타일링

import sys
# 다이나믹 프로그래밍의 경우 점화식을 찾을 것
# 점화식 d[N] = d[N-1]+d[N-2]
d = [0, 1, 2]
for i in range(3, 1001):
  d.append(d[i - 2] + d[i - 1])
n = int(sys.stdin.readline())
print(d[n] % 10007)

백준 11727번 2×n 타일링 2

# 규칙성 찾는 연습을 더 해보자
import sys
d = [0, 1, 3]
for i in range(3, 1001):
  d.append(2*d[i - 2] + d[i - 1])
n = int(sys.stdin.readline())
print(d[n] % 10007)

백준 9095번 1, 2, 3 더하기

# 규칙성찾기에 감을 잡았다
import sys
T = int(sys.stdin.readline())
d = [0, 1, 2, 4]
for i in range(4, 11):
    d.append(d[i - 3] + d[i - 2] + d[i - 1])
for j in range(T):
    n = int(sys.stdin.readline())
    print(d[n] % 10007)