[이것이 취업을 위한 코딩 테스트다 with 파이썬] 6-2강(효율적인 화폐 구성, 병사 배치하기, 금광)

효율적인 화폐 구성

 

이중 for문 사용

N X M 만큼의 시간 복잡도가 소요된다.

  
# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

# 화폐 2개 , 15원 만들기
# 5

# 화페 3개, 4원 만들기
# -1

---

금광

2+4+6+7=19

1 3 3 2 = 첫번째 행, 2 1 4 1 =  두번째 행, 0 6 4 7= 세번째 행

# 테스트 케이스(Test Case) 입력
for tc in range(int(input())):
    # 금광 정보 입력
    n, m = map(int, input().split())
    array = list(map(int, input().split()))

    # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    dp = []
    index = 0
    for i in range(n):
        dp.append(array[index:index + m])
        index += m

    # 다이나믹 프로그래밍 진행
    for j in range(1, m):
        for i in range(n):
            # 왼쪽 위에서 오는 경우 (인덱스 벗어나는지 확인)
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i - 1][j - 1]
            # 왼쪽 아래에서 오는 경우  (인덱스 벗어나는지 확인)
            if i == n - 1:
                left_down = 0
            else:
                left_down = dp[i + 1][j - 1]
            # 왼쪽에서 오는 경우
            left = dp[i][j - 1]
            dp[i][j] = dp[i][j] + max(left_up, left_down, left)

    result = 0
    for i in range(n):
        result = max(result, dp[i][m - 1])

    print(result)

# 2 (테스트 케이스 T)
# 3 4 (N X M)
# 1 3 3 2 2 1 4 1 0 6 4 7
# [1 3 3 2]
# [2 1 4 1]
# [0 6 4 7]

# 2+4+6+7 = 19
# result = 19

+ c++과 java코드는 이코테 깃허브에 있다.

---

병사 배치하기

최적의 해는 5

시간복잡도는 최악의 경우 O(N**)이다

가장 먼저 입력 받은 병사 정보의 순서를 뒤집는다.

가장 긴 증가하는 부분 수열(LIS) 알고리즘을 수행하여 정답을 도출한다.

n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse() # 전투력이 높은 병사가 앞쪽에 오도록 내림차순 해준다

# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n

# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
            dp[i] = max(dp[i], dp[j] + 1)

# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))

# 7 (n 명의 병사)
# 15 11 4 8 5 2 4 (병사들의 전투력)

# 2

총 2,000명이 들어올 수 있기 때문에 dp[2000]