[SWEA] [C] 1859. 백만 장자 프로젝트

문제 링크

풀이 요약

1. 배열 중 가장 높은 수를 구한다
2. 가장 높은 수 전까지의의 이익을 구한다
3. 가장 높은 수 다음 인덱스부터 이를 반복 -> 재귀함수

주의할 점

• 자료형 주의. int의 경우 범위 초과로 테스트케이스 7/10만 정답 처리됨
  -> long long 타입 사용

코드

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

long long buying(int start, int end, int price[], long long profit) {
    if (start > end) { // end case
        return profit;
    }

    int highDay = start; // 첫 인덱스 값을 가장 크다고 가정하고
    for (int i = start+1; i <= end; i++) { // 그 다음 인덱스부터 탐색
        if (price[highDay] < price[i]) {
            highDay = i;
        }
    }
    
    for (int i = start; i < highDay; i++) { // 가장 큰 값까지의 이익 구하기
        profit += price[highDay] - price[i];
    }

    return buying(highDay+1, end, price, profit); // 가장 큰 값 다음 인덱스부터 재탐색
}

int main(void) {
    int T = 0;

    scanf("%d", &T); // 테스트 케이스

    for (int t = 0; t < T; t++) {
        int day = 0;
        scanf("%d", &day); // 날짜 수
        
        int *price = (int*) malloc(sizeof(int) * day); // 가격 저장하는 배열 동적할당

        for (int i = 0; i < day; i++) { // 가격 입력받기
            scanf("%d", &price[i]);
        }

        long long profit = buying(0, day - 1, price, 0); // 자료형 주의. int는 범위 초과

        printf("#%d %lld\n", t + 1, profit);

        free(price);
    }

    return 0;
}

나아갈 점

• 더 효율적인 탐색 방법이 있는가?
• 함수의 파라미터로 배열의 크기를 직접 전달하는 대신 직접 구하고 싶었으나 sizeof(price) / sizeof(int) 값이 계속 2로 나오는 문제 발생

배운 점

• int 자료형의 범위는 약 21억. 이를 넘어가면 long long 타입 등을 사용할 것