기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. 문제 설명

2. 알고리즘적 사고  

이 문제를 해결하기 위해 동적 프로그래밍을 사용할 수 있습니다.

먼저 숫자 문자열을 여러 숫자로 분할하고 nums 배열을 사용하여 각 숫자를 저장합니다. 예를 들어 숫자 문자열 79846은 배열 [7, 9, 8, 4, 6]으로 분할됩니다.

그런 다음 2차원 배열 dp를 정의합니다. 여기서 dp[i][j]는 첫 번째 i 숫자에 j 더하기 기호를 삽입하여 얻을 수 있는 최소값을 나타냅니다. dp[0][0] = 0을 제외하고 dp 배열을 무한대로 초기화합니다.

그런 다음 두 개의 루프를 사용하여 dp 배열을 업데이트합니다. 외부 루프는 숫자 문자열의 각 숫자를 순회하고, 내부 루프는 삽입된 더하기 기호의 수를 순회합니다. 각 dp[i][j]에 대해 숫자 nums[i]를 이전 숫자와 결합하여 새 숫자를 형성하거나 숫자 nums[i]와 이전 숫자 사이에 더하기 기호를 삽입하는 것을 고려할 수 있습니다. 두 경우 중 더 작은 값을 dp[i][j]의 값으로 취합니다.

마지막으로, dp 배열의 마지막 행에 있는 최소값은 구하는 최소값입니다.

3. 코드 구현  

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <stdlib.h>
 
// Helper function to extract integer value from substring
int getNumber(char* str, int start, int end) {
    char buffer[12]; // Buffer large enough for max 10 digits + '0'
    int length = end - start + 1;
    strncpy(buffer, str + start, length);
    buffer[length] = '0';
    return atoi(buffer);
}
 
int main() {
    char str[201];
    int M;
    scanf("%s %d", str, &M);
    
    int n = strlen(str);
    int dp[n+1][M+1];
    
    // Initialize dp array with large numbers
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= M; j++) {
            dp[i][j] = INT_MAX;
        }
    }
    
    // Base case: no splits
    dp[0][0] = 0;
    
    // Dynamic programming to calculate minimum sum
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= M; j++) { // j can be 0 as well
            if (j == 0) {
                dp[i][j] = getNumber(str, 0, i-1);
            } else {
                for (int k = 1; k < i; k++) { // k starts from 1
                    if (dp[k][j-1] != INT_MAX) {
                        int num = getNumber(str, k, i-1);
                        if (dp[k][j-1] + num < dp[i][j]) {
                            dp[i][j] = dp[k][j-1] + num;
                        }
                    }
                }
            }
        }
    }
    
    // Find the minimum value in dp[n][*] with M splits
    int result = INT_MAX;
    for (int i = 0; i <= M; i++) {
        if (dp[n][i] < result) {
            result = dp[n][i];
        }
    }
    
    printf("%dn", result);
    return 0;
}

결과

 결론       

열정을 높이려는 욕구

인내는 산을 평탄하게 할 수 있다

！！！