출처: https://cses.fi/problemset/task/1633

문제 설명

Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.

For example, if n=3, there are 4 ways:

  • 1+1+1 
  • 1+2 
  • 2+1 
  • 3

입력  

The only input line has an integer n.

출력 

Print the number of ways modulo 10^9+7.

입력 예

3

출력 예

4

제약조건

1 <= n <= 10^6

문제 풀이 

주사위를 한번 던져서 나올 수 있는 수는 1~6까지 6가지 경우가 있으므로, 어떤 수 N을 만들기 위해서, 그 전까지 나왔던 경우의 수 (N-1) ~ (N-6)까지 합이 N을 만들 수 있는 경우의 수가 된다.

초기 조건으로 0~5까지 6개의 경우를 입력하고, 6 이상인 경우는 더해서 modulo 연산을 하고,  N이 1~5 인 경우는 초기 조건에서 출력한다.

프로그램 내용

더보기 
...
    vector<long> dp(6, 0);

    /// dp build up n < 6,
    dp[0] = 1; /// init
    dp[1] = 1;  /// dp[0]
    dp[2] = 2;  /// dp[0] + dp[1]
    dp[3] = 4;  /// dp[0] + dp[1] + dp[2]
    dp[4] = 8;  /// dp[0] + dp[1] + dp[2] + dp[3]
    dp[5] = 16; /// dp[0] + dp[1] + dp[2] + dp[3] + dp[4]

    for (int i = 6; i <= n; i++)
        dp[i] = (dp[i-6] + dp[i-5] + dp[i-4] + dp[i-3] + dp[i-2] + dp[i-1]) % 1000000007; 

...

 

Dynamic Programming ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Subarray Divisibility (1662)  (0) 2019.10.09
CSES 2. Subarray Sums II (1661)  (0) 2019.10.09
CSES 8. Minimal Rotation (1110)  (0) 2019.10.09
CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08
CSES 2. Movie Festival II (1632)  (0) 2019.10.07

출처: https://cses.fi/problemset/task/1110

문제 설명

A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of acab are acab, caba, abac, and baca.

Your task is to determine the lexicographically minimal rotation of a string.

입력 

The only input line contains a string of length n. Each character is one of a–z.

출력

Print the lexicographically minimal rotation.

입력 예

acab

출력 예

abac

제약조건

1 <= n <=10^6

문제 풀이 내용

Booth algorithm (link) 을 구현해서 제일 빠른 문자열이 시작하는 위치를 계산한다.

입력 문자열을 2개 연결하고, 계산한 위치부터 원래 입력받은 문자열 길이만큼 출력한다.

프로그램 내용

더보기 
/// https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation
/// Booth algorithm

int booth_search(string str)
{
    string str_work = str + str;    /// Concatenate string to it self to avoid modular arithmetic

    int N = str_work.size();

    vector<int> f(N);            ///  Failure function
    f[0] = -1;

    int k = 0;                   /// Least rotation of string found so far

    for(int j=1; j < N; j++)
    {
        char sj = str_work[j];
        int i = f[j-k-1];
        while ( i != -1 && sj != str_work[k+i+1])
        {
            if ( sj < str_work[k+i+1])
                k = j - i - 1;
            i = f[i];
        }
        if (sj != str_work[k+i+1])
        {
            if ( sj < str_work[k])
                k = j;
            f[j-k] = -1;
        }
        else
            f[j-k] = i+1;
    }

    return k;
}

int main() {
...
	int move_size = booth_search(str_in);
	string str_work = str_in + str_in;
	string out = str_work.substr(move_size, str_in.size());
...

 

String Algorithms( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Subarray Sums II (1661)  (0) 2019.10.09
CSES 3. Dice Combinations (1633)  (0) 2019.10.09
CSES 2. Maximum Subarray Sum II (1644)  (0) 2019.10.08
CSES 2. Movie Festival II (1632)  (0) 2019.10.07
CSES 2. Subarray Sums I (1660)  (0) 2019.10.03

출처: https://cses.fi/problemset/task/1644

문제 설명

Given an array of n integers, your task is to find the maximum sum of values in a contiguous subarray with length between a and b.

입력 

The first input line has three integers n, a and b: the size of the array and the minimum and maximum subarray length.

The second line has n integers x_1,x_2,…,x_n: the array values.

출력 

Print one integer: the maximum subarray sum.

입력 예

8 1 2
-1 3 -2 5 3 -5 2 2

출력 예

8

제약조건

  • 1 <= n <= 2x10^5
  • 1 <= a <= b<= n
  • −10^9 <= x_i <= 10^9

문제 풀이 내용

입력을 받으면서, prefix sum을 계산한다. 특정한 구간 array[a] ~ array[b]의 합은 presum[b+1] - presum[a]를 통해서 구할 수 있다. subarray 길이에 따라서 값을 계산하도록 한다. 처음 알고리즘에서는 길이의 차가 5000이 넘어가면 제한시간에 걸렸다.

알고리즘 수정

prefix sum을 이용해서 읽어 들이면서, prefix sum의 위치가 a 보다 크면 multiset 에 prefix sum 값을 입력하고, 위치가 b 보다 커지면, 그 값들은 multiset에서 제외 시킨다. 부분합을 관리하는 방법은 queue, deque, priority queue 를 사용할 수도 있다.

프로그램 내용

더보기 
...
    vector <long long> num_array(nNum);
    long long sum_array[nNum+1] = {0};

    long long num_max= -1e18;
    long long best = -1e18, sum = -1e18;

    sum_array[0] = 0;

    for (int idx = 0; idx < nNum; ++idx)
        cin >> num_array[idx];
        sum_array[idx+1] = num_array[idx] + sum_array[idx];
        num_max = max(num_max, num_array[idx]);

... /// N^2 
	for (int width=minW; width<= maxW; ++width)
        if (width == 1)
            best = num_max;
        else
            int left=0, right= width;
            long long tsum=sum;
            for (int idx = 0; idx <= nNum - width ; ++idx)
                tsum = sum_array[right] - sum_array[left];
                sum = max(sum, tsum);
                left++;
                right++;

            best = max(best, sum);
...

 

 수정한 프로그램

더보기 
...
    maxW++; /// boundary

    vector <long long> num_array(nNum+1, 0);

    multiset <long long> sum_set;

    long long best = -1e18;

    for (int idx = 1; idx <= nNum; ++idx)
        cin >> num_array[idx];
        num_array[idx] += num_array[idx-1]; /// pre-sum update

        if ( idx - minW >= 0) /// window check
            sum_set.insert(num_array[idx-minW]);

        if ( idx - maxW >= 0) /// window check - too big
            sum_set.erase(sum_set.find(num_array[idx-maxW]));

        if ( sum_set.size()) /// check maximum
            best = max(best, num_array[idx]-*sum_set.begin());
...

 

 

Sorting and Searching ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 3. Dice Combinations (1633)  (0) 2019.10.09
CSES 8. Minimal Rotation (1110)  (0) 2019.10.09
CSES 2. Movie Festival II (1632)  (0) 2019.10.07
CSES 2. Subarray Sums I (1660)  (0) 2019.10.03
CSES 2. Nearest Smaller Values (1645)  (0) 2019.10.03

+ Recent posts

티스토리툴바