[8/23] 이코테 DP

2. 1로 만들기

218 실패

내 코드

dp = [0] * 30001

x = int(input())

for i in range(2, x+1):
    
    d[i] = d[i-1] + 1
    
    if ( i % 2 == 0 ):
        d[i] = min(d[i], d[i // 2] + 1)
        
    if ( i % 3 == 0 ):
        d[i] = min(d[i], d[i // 3] + 1)
        
    if ( i % 5 == 0 ):
        d[i] = min(d[i], d[i // 5] + 1)
        
    print(i, d[i])
        
print(d[x])

로직

• DP + 메모이제이션

3. 개미 전사

221 실패

내 코드

n = int(input())
arr = list(map(int, input().split()))

d = [0] * 100

d[0] = arr[0]
d[1] = max(arr[0], arr[1])

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

로직

• DP + 메모이제이션

---

4. 바닥 공사

224

내 코드

n = int(input())
d = [0] * 1001

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

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

answer = d[n] % 796796
print(answer)

로직

• DP + 메모이제이션

---

5. 효율적인 화폐 구성

227

내 코드

n, m = map(int, input().split())
arr = []
for _ in range(n):
    temp = int(input())
    arr.append(temp)

dp = [10001] * (m+1)
dp[0] = 0

for i in range(n):
    for j in range(arr[i], m+1):
        if ( dp[j - arr[i]] != 10001 ):
            dp[j] = min(dp[j], dp[j - arr[i]] + 1)

if dp[m] == 10001:
    print(-1)
else:
    print(dp[m])

로직

• DP + 메모이제이션

---

<31> 금광

375

내 코드

from collections import deque

t = int(input())
for _ in range(t):
    
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))
    arr = deque(arr)
    answer = 0  # 최댓값

    gold = [[] * i for i in range(m)]
    for i in range(n):
        for j in range(m):
            temp = arr.popleft()
            gold[j].append(temp)

    new = [[] * i for i in range(m)]
    new[0] = gold[0]

    for i in range(1, m):
        for j in range(n):
            # 맨 왼쪽
            if ( j == 0 ):
                temp = max(new[i-1][:2])
                temp += gold[i][j]
                new[i].append(temp)
            # 맨 오른쪽
            elif ( j == (n-1) ):
                temp = max(new[i-1][-2:])
                temp += gold[i][j]
                new[i].append(temp)
            else:
                temp = max(new[i-1][j-1:j+2])
                temp += gold[i][j]
                new[i].append(temp)        

    print(max(new[-1]))

로직

1. 2차원 배열을 재배치해서 밑으로 내려갈 수 있게 했다.
2. 가장 큰 값을 찾아 내려간다. (위치에 따라 인덱스 조정)
3. 행렬을 뒤집어 주는 작업이 필요하다.

---

<32> 정수 삼각형

376 (실버1) 문제

내 코드

n = int(input())
arr = []

for i in range(1, n+1):
    arr.append(list(map(int, input().split())))

for j in range(1, n):
    for k in range(len(arr[j])):
        # 처음
        if (k == 0):
            arr[j][k] = arr[j][k] + arr[j-1][0]
            
        # 마지막
        elif (k == (len(arr[j])-1)):
            arr[j][k] = arr[j][k] + arr[j-1][-1]
            
        # 중간
        else:
            arr[j][k] = arr[j][k] + max(arr[j-1][k-1], arr[j-1][k])
            
print(max(arr[-1]))

로직

내려가면서 진행

피드백

• 굳이 새로운 리스트를 만들 필요 없이, 그냥 기존 리스트에 덮어서 저장하면 된다.

---

<33> 퇴사

377 (실버4) 실패 문제

내 코드 (답지)

n = int(input())
t, p = [0], [0]
dp = [0] * (n+2)  # 이거 인덱스를 1 늘려줬어야 함
max_value = 0

for _ in range(1, n+1):
    x, y = map(int, input().split())
    t.append(x)
    p.append(y)
    
for i in range(n, 0, -1):
    time = t[i] + i
    
    if time <= (n+1):
        dp[i] = max(p[i] + dp[time], max_value)
        max_value = dp[i]
        
    else:
        dp[i] = max_value
        
print(max_value)
print(dp)

로직

• 거꾸로 접근하기
• 인덱스와 시간이 헷갈려서 +1 해서 맞춰줬다.

---

<34> 병사 배치하기

380 (실버) 문제

내 코드 (실패)

n = int(input())
array = list(map(int, input().split()))

array.reverse()
print(array)

dp = [1] * n

for i in range(1, n):
    for j in range(0, i):
        print(i, j)
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(dp)
print(n - max(dp))

로직

• 횟수를 누적함

---

<35> 못생긴 수

381

내 코드

n = int(input())
arr = [1]

cnt = 0
while True:
    if (len(arr) >= n ):
        print(arr[n-1])
        break
    
    if (arr[cnt]*2 not in arr):
        arr.append(arr[cnt]*2)
    if (arr[cnt]*3 not in arr):
        arr.append(arr[cnt]*3)
    if (arr[cnt]*5 not in arr):
        arr.append(arr[cnt]*5)
    
    arr.sort()
    
    cnt += 1

로직

• 1부터 시작해서 X2, X3, X5 한 수를 리스트에 넣고 정렬한다.

---

<36>

포기...