[백준 14501번/C언어] 퇴사, 동적계획법(DP, Dynamic Programming)으로 풀이

백준 14501번 문제를 Dynamic Programming (DP, 동적계획법)을 이용하여 풀어보았습니다.

백준 14501번: https://acmicpc.net/problem/14501

14501번: 퇴사

 

 

문제 내용은 다음과 같습니다. 

 

 

 

 

 이 문제는 앞서 언급한 대로 동적계획법으로 푸는 문제입니다. 혹시 동적 계획법이 익숙하지 않은 분들이라면 더 쉬운 동적계획법 문제부터 차근히 풀어보시는 것을 추천드립니다.  저도 그러한 과정을 거쳤고, 아래 링크 글부터 순서대로 동적계획법 문제들이 쭉 풀이되어 있는 것을 제 블로그에서도 확인하실 수 있습니다.

https://programming-diary-ina.tistory.com/7 

[백준 2579번/C언어] 계단 오르기, 동적계획법으로 풀이

 

 

 

 

제가 문제에 접근한 방법은 우선 입력받은 정보를 저장할 때에, 수익을 받을 수 있는 날을 기준으로 저장을 했습니다. 즉, 첫 번째 날 상담에 3일이 걸린다면 3일 차가 끝나고, 수익을 받을 수 있다고 생각하는 것입니다. 그래서 이 수익 받을 수 있는 날을 기준으로 정렬하여서 linked list로 저장을 해두었습니다.

 그 이후 동적계획법을 활용해, N이 1이라면 받을 수 있는 최대 수익에서 N이 N이라면 받을 수 있는 최대 상담료까지 차근히 점화식을 통해 계산하여 배열에 저장해나갔습니다. 이때 사용한 점화식은 다음과 같습니다.

F(N) = Max(F(N - 1), N일차 수익 + F(N - N일차 수익을 만드는 데 걸리는 시간))

 

 즉, 두 가지 경우 중 더 큰 경우를 N일차 배열에 저장하면 되는 것인데요, 첫 번째 경우는 F(N - 1)로 N-1일차 배열을 그대로 옮겨오는 것입니다. N일차에 얻을 수 있는 수익이 없거나, N일차 수익을 얻기 위해서 소요되는 시간 때문에 다른 수익을 포기하는 것의 효용이 더 작을 때에 이 경우를 선택하게 됩니다. 두 번째 경우는 N일차에 얻을 수 있는 수익에 (N - N일차 수익을 만드는 데 걸리는 시간) 일차까지의 최대 수익을 더하는 방식입니다. 예를 들어 5일 차에 얻을 수 있는 수익이 10이고 소요 기간이 이틀인데, 4일 차 수익이 5밖에 되지 않는다면 과감하게 4일 차 수익을 포기하고 5일 차 수익을 선택할 수 있습니다. 따라서 5일차 수익에 3일 차까지의 최대 수익을 더하는 것이 5일 차까지의 최대 수익이 될 것입니다. 

 

 

 

 이를 바탕으로 코드를 보겠습니다. 우선 코드를 보면 크게 두 파트로 나누어볼 수 있습니다. 수익을 받는 날을 기준으로 정렬하며 데이터를 저장해 나가는 부분과 정렬된 데이터를 바탕으로 N일차의 최대 수익을 계산하는 부분입니다.

 

 정렬하며 데이터를 저장해나가는 부분은 LINKED 구조체부터, makeElem() 함수, 그리고 makeList() 함수까지로 볼 수 있습니다. 우선 LINKED 구조체는 정렬된 linked list를 만들기 위한 구조체입니다. requiredDays에는 해당 수익을 위해서 소요되는 시간을 저장하고, salaryDay에는 수익을 받는 날(즉 1일 차에 주어진 3일이 소요되는 상담이라면 salaryDay는 3이 됩니다)을, 그리고 value에는 받을 수 있는 수익이 저장됩니다. next의 경우는 linked list를 만들기 위한 요소에 해당합니다. 

 makeElem() 함수는 생성될 linked list 내 노드 하나를 생성하는 역할을 합니다. 노드를 생성할 일이 많은데, 그때마다 메모리를 할당하고 요소 하나하나 값을 받으려면 코드가 너무 길어지기 때문에 함수로 만들어줬습니다.

 makeList() 함수는 데이터를 입력받아 정렬하여 linked list를 생성하는 역할을 하는 함수입니다. 소요되는 날짜인 d와 수익인 v를 입력받아 첫번째 노드인 head를 먼저 채워줍니다. 그러고 나서는 N-1번 반복하면서 알맞게 정렬되기 위한 해당 노드의 위치를 찾아 넣어주는 방식으로 linked list를 만들게 됩니다. 이때 1일 차부터 차례로 데이터가 입력되므로, for문을 통해 i를 하나씩 증가시켜 가며 며칠차인지를 확인하는 역할을 합니다. 이를 salaryDay 요소를 찾을 때도 활용해 줍니다. 정렬하는 과정을 좀 더 자세히 보면, 우선 salaryDay를 계산해 주고, 만약 이것이 N보다 크다면 저장하지 않고 넘깁니다. 왜냐하면 해당 수익은 이미 퇴사한 이후이므로 받을 수 없는 수익이기 때문입니다. N보다 크지 않다면 이제 linked list 내 저장할 알맞은 위치를 찾아주면 됩니다. 만약 head에 저장된 salaryDay보다 작다면 head를 바꿔주어야 하고 그렇지 않다면 linked list를 순회하며 자신보다 큰 salaryDay를 가진 첫 노드를 만나면 그 바로 앞에 저장해 주게 됩니다. 

 

 정렬된 데이터를 바탕으로 N일차의 최대 수익을 계산하는 부분은 main 함수 내에 구현되어 있습니다. 우선 dp배열을 선언해줍니다. 입력받을 수 있는 최댓값이 15이므로 15+1인 16 크기의 배열로 만들어줍니다. 이제 dp[n]에 n일차 최대 수익을 저장하게 될 것입니다. 우선 0일 차 수익은 당연히 0원이므로, 0을 저장해 줍니다. 그리고 curr 변수를 만들어줘서 linked 리스트를 순회할 수 있도록 준비합니다.

 이제 1일차부터 N일차까지 순회하면서 최대 수익을 하나씩 찾아주면 됩니다. i일차의 초기값으로는 i-1일 차의 최댓값을 먼저 저장해 줍니다. 이제 i일차에 벌 수 있는 수익들을 하나씩 확인하면서 i-1일 차의 최댓값보다 더 큰 값이 나온다면 이 값을 대체해 주는 방식으로 i일차의 최대 수익을 찾을 수 있습니다. 일단 i일차의 수익을 temp 변수에 저장해 주고, i일차에서 해당 수익을 버는 데 걸리는 시간을 뺀 일자의 최대 수익을 더해주어 i일차까지의 수익을 구해줍니다. 이렇게 구한 i일차까지의 수익이 i-1일 차까지의 수익보다 크다면 해당 수익이 아니라면 i-1일 차의 수익이 저장된 상태가 될 것입니다. 만약 i일차에 선택 가능한 다른 수익 옵션이 있다면 모두 순회해줘야 하므로 현재 노드의 salaryDay가 i일 때 반복하는 while문을 사용해 줬습니다. 

 이렇게 dp 배열을 모두 채워줬다면 이제 메모리 할당했던 것들을 해제해주고, N일차의 최대 수익인 dp[N]을 출력해 주면 마무리됩니다. 

#include <stdio.h>
#include <stdlib.h>

typedef struct LINKED {
    int requiredDays;
    int salaryDay;
    int value;
    struct LINKED *next;
} Linked;

Linked *makeElem(int requiredDays, int salaryDay, int value, Linked *next) {
    Linked *elem = (Linked *)malloc(sizeof(Linked));
    if (elem == NULL) return NULL;
    
    elem->requiredDays = requiredDays;
    elem->salaryDay = salaryDay;
    elem->value = value;
    elem->next = next;
    return elem;
}

Linked *makeList(int N) {
    int d, v;
    scanf("%d%d", &d, &v);
    Linked *head = makeElem(d, d, v, NULL);
    if (head == NULL) return NULL;
    
    for (int i = 1; i < N; i++) {
        scanf("%d%d", &d, &v);
        int s = d + i;
        if (s > N) {
            continue;
        } else if (s < head->salaryDay) {
            head = makeElem(d, s, v, head);
            if (head == NULL) return NULL;
        } else {
            Linked *curr = head;
            while (curr->next && curr->next->salaryDay < s) curr = curr->next;
            curr->next = makeElem(d, s, v, curr->next);
            if (curr->next == NULL) return NULL;
        }
    }
    
    return head;
}

int main() {
    int N;
    scanf("%d", &N);
    
    Linked *head = makeList(N);
    if (head == NULL) return 1;
    
    int dp[16];
    dp[0] = 0;
    Linked *curr = head;
    for (int i = 1; i <= N; i++) {
        dp[i] = dp[i-1];
        while (curr && curr->salaryDay == i) {
            int temp = curr->value;
            if ((i - curr->requiredDays) > 0)
                temp += dp[i - curr->requiredDays];
            if (temp > dp[i]) dp[i] = temp;
            curr = curr->next;
        }
    }
    
    while (head) {
        curr = head->next;
        free(head);
        head = curr;
    }
    
    printf("%d", dp[N]);
}