이것이 취업을 위한 코딩 테스트다 CHAPTER 16 다이나믹 프로그래밍 문제

Q 31. 금광

'''

    Chapter 16. 금광

    접근법 1

        금광 이동 경우 : 왼쪽 위, 왼쪽, 왼쪽 아래에서 오는 경우

            3가지 경우 중 큰 값 선택하기

       

        indexError을 위해 위 아래에 [0]*m 추가

'''

import sys
input = sys.stdin.readline

TC = int(input())
for _ in range(TC):
    n,m = map(int,input().split())
    arr = list(map(int,input().split()))
    # 금광 n*m
    # 위 아래에 [0]*m 행 추가
    arr = [[0]*m] + [arr[i:i+m] for i in range(0,n*m,m)] + [[0]*m]
    
    for c in range(1,m):
        for r in range(1,n+1):
            # 왼쪽 위, 왼쪽, 왼쪽 아래 중 큰 값 추가
            arr[r][c] += max(arr[r-1][c-1], arr[r][c-1], arr[r+1][c-1])

    answer = 0
    # 가장 큰 값 구하기
    for i in range(1,n+1):
        if arr[i][m-1] > answer:
            answer = arr[i][m-1]

    print(answer)

 

Q 32. 정수 삼각형

'''

    Chapter 16. 정수 삼각형

    접근법 1

        아래층 기준으로 보기

            왼쪽 위 대각선 혹은 오른쪽 위 대각선에서 내려온다.

            이 층의 가장 첫번째 수는 오른쪽 위 대각선만 존재

            이 층의 가장 마지막 수는 왼쪽 위 대각선만 존재

        최댓값 구하기

'''

import sys
input = sys.stdin.readline

n = int(input())
triangle = [list(map(int,input().split())) for _ in range(n)]

for r in range(1,n):
    for c in range(len(triangle[r])):
        # 오른쪽 위 대각선만 존재
        if c == 0:
            triangle[r][c] += triangle[r-1][c]
        # 왼쪽 위 대각선만 존재
        elif c == len(triangle[r])-1:
            triangle[r][c] += triangle[r-1][c-1]
        # 양쪽 다 존재
        else:
            triangle[r][c] += max(triangle[r-1][c-1],triangle[r-1][c])

print(max(triangle[-1]))

 

Q 33. 퇴사 2

'''

    Chapter 16. 퇴사 2

   

    접근법 1

        날짜를 순서대로 확인

            해당 일 이전까지의 이익 == money

            해당 일의 상담이 근무 종료 전 마무리가 가능한 경우

                상담을 하는 것과 하지 않는 것 중 이익이 큰 경우 선택

           

    접근법 2

        날짜를 거꾸로 확인

            1. 해당 일의 상담이 근무종료 전 마무리가 가능한 경우

                1-1. 이 상담이 이익에 도움이 되는지 확인해야 함

                    상담을 하는 것과 상담을 하지 않는 것 중 이익이 큰 경우 선택

            2. 불가능한 경우

                내일의 이익이 오늘의 이익

                   

'''

import sys
input = sys.stdin.readline

# 근무 일
N = int(input())
# 상담
t = [] # 시간
p = [] # 이익
for i in range(N):
    ti, pi = map(int, input().split())
    t.append(ti)
    p.append(pi)

'''
    날짜를 순서대로 확인
'''
dp = [0]*(N+1)
for i in range(N):
    # i일 이전까지의 이익
    money = max(money,dp[i])
    # 이 상담을 근무 종료 전 마무리 가능?
    if i + t[i] <= N:
        # 상담을 하는 경우와 하지 않는 경우 이익 따져보기 
        dp[i+t[i]] = max(dp[i+t[i]], money + p[i])

print(max(dp))
# 메모리 167844	시간 2588

'''
    날짜를 거꾸로 확인
'''
dp = [0]*(N+1)
for day in range(N-1,-1,-1):
    new_day = day + t[day]
    # 해당 일의 상담을 근무 종료 전 마무리 가능한 경우
    if new_day <= N:
        # 근무를 하는 경우 / 근무를 하지 않는 경우 중 최대 이익이 나는 것 고르기
        dp[day] = max(dp[new_day] + p[day],dp[day+1])
    # 해당 일의 상담을 근무 종료 전 마무리 불가능 한 경우
    else:
        dp[day] = dp[day+1]

print(dp[0])
# 메모리 167844	시간 2096

 

Q 34. 병사 배치하기

'''

    Chapter 16. 병사 배치하기

    접근법 1

        병사 수 최대 2000->2000*2000 = 4,000,000 연산 가능

            파이썬은 1초에 2000만 = 20,000,000 번 연산이 가능하다고 생각

        dp[i] == 0번째 병사부터 i번째 병사까지 중 내림차순으로 배치 가능한 병사 수

'''

import sys
input = sys.stdin.readline

N = int(input())
power = list(map(int,input().split()))

dp = [1]*(N)
for i in range(N):
    # 0~i 병사들의 내림차순 가능 병사 수
    for j in range(i):
        if power[i] < power[j]:
            dp[i] = max(dp[i],dp[j]+1)

# 열외시켜야 하는 병사 수 == 전체 병사 수 - 내림차순 가능 병사 수
print(N - max(dp))

 

Q 35. 못생긴 수

'''

    Chapter 16. 못생긴 수

    접근법 1

        해결이 안되서 답지 참고

        못생긴 수를 앞에서부터 하나씩 찾기

        못생긴 수에 2,3 혹은 5를 곱한 수 또한 못생긴 수!!

       

        작은 못생긴 수부터 찾기위해 n_2,n_3,n_5 값 저장

            n_2 : 현재 만든 못생긴 수 중 2를 곱한 적 없는 가장 작은 수

            i_2 : 현재 만든 못생긴 수 중 2를 곱한 적 없는 가장 작은 수의 인덱스

'''

import sys
input = sys.stdin.readline

n = int(input())
ugly = [0]*(n+1)
# 첫번째 못생긴 수 
ugly[0] = 1

# 2배, 3배, 5배를 위한 인덱스
i_2 = i_3 = i_5 = 0

# 다음 못생긴 수 구할 때 
n_2,n_3,n_5 = 2,3,5

# n번째 못생긴 수 찾기
for i in range(1,n):
    # 가능한 곱셈 결과 중에서 가장 작은 수를 선택
    ugly[i] = min(n_2,n_3,n_5)
    
    # 2를 곱해야 하는 경우
    if ugly[i] == n_2:
        i_2 += 1
        n_2 = ugly[i_2]*2
    
    # 3를 곱해야 하는 경우
    elif ugly[i] == n_3:
        i_3 += 1
        n_3 = ugly[i_3]*3

    # 5를 곱해야 하는 경우
    elif ugly[i] == n_5:
        i_5 += 1
        n_5 = ugly[i_5]*5
    
print(ugly[n-1])

 

Q 36. 편집 거리

'''

    Chapter 16. 편집 거리

    접근법 1  

        해결이 안되서 답지 참고

        A문자를 B로 만들기 -> 2차원 테이블로 해결해보자

            A(star)는 행, B(car)는 열

                c a r

              0 1 2 3        

            s 1

            t 2

            a 3

            r 4

        1. 문자가 같은 경우

            dp[r][c] = dp[r-1][c-1]

        2. 문자가 다른 경우

            2-1. 삽입

                삽입하면 다음 비교는 r문자와 c의 다음 문자가 된다

                dp[r][c] = dp[r][c-1] + 1

            2-2. 삭제

                삭제하면 다음 비교는 r의 다음 문자와 c문자가 된다

                dp[r][c] = dp[r-1][c] + 1

            2-3. 교체

                교체하면 다음 비교는 r의 다음 문자와 c의 다음 문자가 된다

                dp[r][c] = dp[r-1][c-1] + 1

   

'''

import sys
input = sys.stdin.readline

# A -> B
A = input().rstrip()
a = len(A)
B = input().rstrip()
b = len(B)

dp = [[0]*(a+1) for _ in range(b+1)]
# dp 초기 설정
for c in range(1,b+1):
    dp[0][c] = c
for r in range(1,a+1):
    dp[r][0] = r

for r in range(1,a+1):
    for c in range(1,b+1):
        # r행 문자와 c열 문자가 같은가?
        if A[r] == B[c]:
            dp[r][c] = dp[r-1][c-1]
        # 다른 경우
        # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중 최소 비용
        else:
            dp[r][c] = 1 + min(dp[r][c-1], dp[r-1][c], dp[r-1][c-1])
print(dp[a][b])