[이것이 코딩 테스트다 with Python]_29_다이나믹 프로그래밍 기초 문제 풀이

220211 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=tWX6FZwwQMI&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=29 

 

 

 

 

 

 

 

 

 

 

 

< 문제1 > 개미전사

: 최소한 한 칸 이상 떨어진 식량창고를 약탈하자!

: 인접한 식량창고 공격받으면 들킨다

: 식량창고 N개에 대한 정보가 주어졌을 때, 얻을 수 있는 식량의 최대값 구하기

식량 선택 8번

3, 5, 해서 8개 얻기

1) a(i) = i번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최대값)

2) k(i) = i번쨰 식량창고에 있는 식량의 양

 

• python

# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1]) 
for i in range(2, n):
    d[i] = max(d[i - 1], d[i - 2] + array[i])

# 계산된 결과 출력
print(d[n - 1])

• c++

#include <bits/stdc++.h>

using namespace std;

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
int d[100];
int n;
vector<int> arr;

int main(void) {
    // 정수 N을 입력받기
    cin >> n;
    // 모든 식량 정보 입력받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
    d[0] = arr[0];
    d[1] = max(arr[0], arr[1]);
    for (int i = 2; i < n; i++) {
        d[i] = max(d[i - 1], d[i - 2] + arr[i]);
    }

    // 계산된 결과 출력
    cout << d[n - 1] << '\n';
}

 

• java

import java.util.*;

public class Main {

    // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
    public static int[] d = new int[100];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 정수 N을 입력받기
        int n = sc.nextInt();

        // 모든 식량 정보 입력받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
        d[0] = arr[0];
        d[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < n; i++) {
            d[i] = Math.max(d[i - 1], d[i - 2] + arr[i]);
        }

        // 계산된 결과 출력
        System.out.println(d[n - 1]);
    }
}

 

 

 

 

 

 

 

< 문제2 > 1로 만들기

: 정수 X 가 주어졌을 때 연산을 사용하는 횟수의 최소값 구하기

1) 5로 나누어 떨어지면 5로 나누기

2) 3으로 나누어떨어지면, 3으로 나누기

3) 2로 나누어떨어지면, 2로 나누기

4) 1 빼기

EX) 26 -> 25 -> 5 -> 1

 

• python

# 정수 X를 입력 받기
x = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1000001

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for i in range(2, x + 1):
    # 현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    # 현재의 수가 5로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

• c++

#include <bits/stdc++.h>

using namespace std;

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
int d[30001];
int x;

int main(void) {
    cin >> x;
    // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
    for (int i = 2; i <= x; i++) {
        // 현재의 수에서 1을 빼는 경우
        d[i] = d[i - 1] + 1;
        // 현재의 수가 2로 나누어 떨어지는 경우
        if (i % 2 == 0)
            d[i] = min(d[i], d[i / 2] + 1);
        // 현재의 수가 3으로 나누어 떨어지는 경우
        if (i % 3 == 0)
            d[i] = min(d[i], d[i / 3] + 1);
        // 현재의 수가 5로 나누어 떨어지는 경우
        if (i % 5 == 0)
            d[i] = min(d[i], d[i / 5] + 1);
    }
    cout << d[x] << '\n';
}

• java

import java.util.*;

public class Main {

    // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
    public static int[] d = new int[30001];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();

        // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
        for (int i = 2; i <= x; i++) {
            // 현재의 수에서 1을 빼는 경우
            d[i] = d[i - 1] + 1;
            // 현재의 수가 2로 나누어 떨어지는 경우
            if (i % 2 == 0)
                d[i] = Math.min(d[i], d[i / 2] + 1);
            // 현재의 수가 3으로 나누어 떨어지는 경우
            if (i % 3 == 0)
                d[i] = Math.min(d[i], d[i / 3] + 1);
            // 현재의 수가 5로 나누어 떨어지는 경우
            if (i % 5 == 0)
                d[i] = Math.min(d[i], d[i / 5] + 1);
        }

        System.out.println(d[x]);
    }
}

 

 

 

 

< 문제3 > 효율적인 화폐 구성

: N 가지 종류의 화폐 있음

: 화폐들 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하기

: M 원을 만들기 위한 최소한의 화폐 개수 구하기

 

 

 

• python

# 정수 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])

• c++

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> arr;

int main(void) {
    // 정수 N, M을 입력받기
    cin >> n >> m;
    
    // N개의 화폐 단위 정보를 입력 받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    // 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
    vector<int> d(m + 1, 10001);

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

    // 계산된 결과 출력
    if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
        cout << -1 << '\n';
    }
    else {
        cout << d[m] << '\n';
    }
}

• java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 정수 N, M을 입력받기
        int n = sc.nextInt();
        int m = sc.nextInt();

        // N개의 화폐 단위 정보를 입력 받기
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 
        int[] d = new int[m + 1];
        Arrays.fill(d, 10001);

        // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
        d[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = arr[i]; j <= m; j++) {
                // (i - k)원을 만드는 방법이 존재하는 경우
                if (d[j - arr[i]] != 10001) {
                    d[j] = Math.min(d[j], d[j - arr[i]] + 1);
                }
            }
        }

        // 계산된 결과 출력
        if (d[m] == 10001) { // 최종적으로 M원을 만드는 방법이 없는 경우
            System.out.println(-1);
        }
        else {
            System.out.println(d[m]);
        }
    }
}

 

 

 

 

 

 

< 문제4 > 금광

: n x m 크기의 금광이 있다

: 각 칸은 특정한 크기의 금이 들어가 있따

: 맨 처음에는 첫 열 어느 행에서든 출발 가능

: 이후에 m-1 번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야함

: 채굴자가 얻을 수 있는 금의 최대 크기 출력

1) 왼쪽 위에서 오는 경우

2) 왼쪽 아래에서 오는 경우

3) 왼족에서 오는 경우

=> 가장 많은 금을 가지고 있는 경우를 테이블에 갱신

max(왼쪽 위, 왼쪽 아래, 왼쪽)

 

 

 

• python

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)

 

 

 

 

< 문제5 > 병사 배치하기

: N 명의 병사가 무작위로 나열

: 전투력이 높은 병사가 앞쪽에 오도록 내림차순!

: 남아 있는 병사의 수가 최대가 되도록 하기 위해 열외시켜야 하는 병사의 수 출력

: 가장 긴 증가하는 부분 수열 (LIS)

: 특정 위치 병사는 예외

 

 

• python

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))