알고리즘 스터디 3주차 마무리 [dp]

백준 문제

 

3주차 목표:

백준 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

1463

n = int(input())

# 최대 수 제한
d = [0] * 1000001

d[0] = 0
d[1] = 0
d[2] = 1
d[3] = 1

for i in range(2, n+1):
    # 2와 3으로 나누어 떨어지지 않는 경우 ( -1 에 대한 연산만 수행 )
    d[i] = d[i-1] + 1

    print('-------')
    print('index: ', i, 'value: ', d[i]);

    # 2로 나누어 떨어지는 경우와 3으로 나누어 떨어지지 않는 경우 중 최솟값을 선택
    # 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        print('index: ', i, 'd[i//2]: ', d[i//2], 'd[i//2] + 1: ', d[i//2] + 1);
        d[i] = min(d[i], d[i//2] + 1)
        
    # 3으로 나누어 떨어지는 경우
    # 3이 2보다 우선순위가 높기 때문에 2로 나누어 떨어지는 경우와 동시에 3으로 나누어 떨어지는 경우가 존재할 수 있음
    if i % 3 == 0:
        print('index: ', i, 'd[i//3]: ', d[i//3], 'd[i//3] + 1: ', d[i//3] + 1);
        d[i] = min(d[i], d[i//3] + 1)

print(d[n])

출력 예시

#입력값: 7

-------
index:  2 value:  1
index:  2 d[i//2]:  0 d[i//2] + 1:  1
-------
index:  3 value:  2
index:  3 d[i//3]:  0 d[i//3] + 1:  1
-------
index:  4 value:  2
index:  4 d[i//2]:  1 d[i//2] + 1:  2
-------
index:  5 value:  3
-------
index:  6 value:  4
index:  6 d[i//2]:  1 d[i//2] + 1:  2
index:  6 d[i//3]:  1 d[i//3] + 1:  2
-------
index:  7 value:  3

11726

n = int(input())

#11726 백준

# 2xn 타일링
d = [0] * 1001

# 기본 값 세팅 ( 반복전, 연산에  필요한 기본값을 저장해 줌 ) 
d[1] = 1
d[2] = 2

for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

# 10007은 소수이기 때문에 나누어 떨어지는 수가 없음
print(d[n] % 10007)

11727

# 11727 백준
n = int(input())

d = [0] * 1001

d[1] = 1
d[2] = 3
d[3] = 5

for i in range(4, n+1):
    d[i] = d[i-1] + d[i-2] * 2;

print(d[n] % 10007)

9095

T = int(input())

d = [0] * 11

d[1] = 1
d[2] = 2
d[3] = 4

for i in range(4,11):
    d[i] = d[i-3] + d[i-2] + d[i-1]

for i in range(0,T):
    n = int(input())
    print(d[n])

10844

# 풀지 못함

11057

n = int(input())
dp = [1]*10
for i in range(1,n) :
    for j in range(1,10) :
        dp[j] += dp[j-1]

print(sum(dp)%10007)

2193

n = int(input())
dp = [0] * 91
dp[1] = 1
dp[2] = 1

for i in range(2, n + 1):
    dp[i] = dp[i - 2] + dp[i - 1]

print(dp[n])

9465

# 풀지 못함..