๋ณธ๋ฌธ์œผ๋กœ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๐Ÿ”—๋ฌธ์ œ ๋ณด๋Ÿฌ๊ฐ€๊ธฐ
 

10844๋ฒˆ: ์‰ฌ์šด ๊ณ„๋‹จ ์ˆ˜

์ฒซ์งธ ์ค„์— ์ •๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

www.acmicpc.net

 

๐Ÿง‘๐Ÿป‍๐Ÿ’ปํ’€์ด ๊ณผ์ •

N์ž๋ฆฌ ์ˆซ์ž์—์„œ ์ผ์˜ ์ž๋ฆฌ๊ฐ€ 0 ~ 9๋กœ ๋๋‚˜๋Š” ๊ณ„๋‹จ ์ˆ˜๋“ค์˜ ๊ฐœ์ˆ˜๋ฅผ ์•Œ์•„๋ด…์‹œ๋‹ค. ๋จผ์ €, \( N = 1\)์ผ ๋•Œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

 

[ N = 1 ์ผ ๋•Œ ]

i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9
0 1
1 1 1 1 1 1 1 1

 

[ N = 2 ์ผ ๋•Œ ]

i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9
1 1 2 2 2 2 2 2 2 1

 

[ N = 3 ์ผ ๋•Œ ]

i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9
1 3 3 4 4 4 4 4 3 2

 

 

์ด ์ •๋„๊นŒ์ง€ ์ง„ํ–‰ํ•ด๋ณด๋‹ˆ, ๊ทœ์น™์„ฑ์ด ๋ณด์ด๊ธฐ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.

N ์ž๋ฆฌ ์ˆซ์ž์—์„œ i ์ˆซ์ž๋กœ ๋๋‚˜๋Š” ๊ณ„๋‹จ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ์ €์žฅํ•˜๋Š” ๋ฐฐ์—ด์„ dp[N][i]๋ผ๊ณ  ํ•œ๋‹ค๋ฉด, ๊ทœ์น™์„ฑ์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.

dp[N][0] = dp[N-1][1]
dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1];    (i > 0 and i < 9)
dp[N][9] = dp[N-1][8]

 

์ฆ‰, ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ์„ ์ด์šฉํ•˜์—ฌ N = 1์ผ ๋•Œ์˜ i๊ฐ’๋“ค์„ ๋ฐ”ํƒ•์œผ๋กœ N = 2, N = 3์˜ ๊ฐ’๋“ค์„ ์ฐจ๋ก€๋Œ€๋กœ ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋˜ํ•œ, ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ์— ์‚ฌ์šฉํ•  ๋ฐฐ์—ด์€ \( 2 \times 10 \) ํฌ๊ธฐ๋งŒ ๊ฐ€์ง„๋‹ค๋ฉด, ๋ชจ๋“  N์— ๋Œ€ํ•œ ๊ณ„๋‹จ ์ˆ˜ ๊ฐœ์ˆ˜๋ฅผ ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

 

์ด๊ฒƒ์ด ์–ด๋–ป๊ฒŒ ๊ฐ€๋Šฅํ• ๊นŒ์š”? ์ €๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋ฐฉ๋ฒ•์œผ๋กœ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค.

๋จผ์ €, ํ–‰์„ ๊ฐ€๋ฆฌํ‚ค๋Š” ๋ณ€์ˆ˜๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด 2๊ฐœ ์„ ์–ธํ•ฉ๋‹ˆ๋‹ค.

int writeBufferIndex = 0, readBufferIndex = 1;
  • writeBufferIndex๋Š” readBufferIndex์˜ ํ–‰์—์„œ ์ฝ์–ด์™€ ์ƒˆ๋กœ ๊ฐ’์„ ์“ฐ๊ฒŒ ๋˜๋Š” ํ–‰์„ ์˜๋ฏธํ•ฉ๋‹ˆ๋‹ค.
  • ์œ„์—์„œ ๋งŒ๋“ค์—ˆ๋˜ ์ ํ™”์‹์— ๋น„์œ ํ•˜์ž๋ฉด, writeBufferIndex๋Š” NreadBufferIndex๋Š” N - 1์— ํ•ด๋‹นํ•œ๋‹ค๊ณ  ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  • ํ•œ ํ–‰์— ๋Œ€ํ•˜์—ฌ ๋ชจ๋‘ ์—ฐ์‚ฐ์ด ๋๋‚ฌ๋‹ค๋ฉด, writeBufferIndex์™€ readBufferIndex๊ฐ€ ์„œ๋กœ ๊ฐ’์„ ๊ตํ™˜ํ•จ์œผ๋กœ์จ, ์—ญํ• ์„ ๋ฐ”๊ฟ”์„œ ๋‹ค์‹œ ์—ฐ์‚ฐ์„ ์ด์–ด๋‚˜๊ฐ€๊ฒŒ ๋ฉ๋‹ˆ๋‹ค.

 

N์ด ํด์ˆ˜๋ก 2์ฐจ์› ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๊ฐ€ ์ปค์ง€๊ฒŒ ๋˜์–ด ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๋งŽ์ด ์“ฐ๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ์ €๋Š” ์œ„ ์ ํ™”์‹์„ ๋„์ถœํ•˜๋Š” ๊ณผ์ •์—์„œ ํ–‰์ด N๊ฐœ๊นŒ์ง€ ํ•„์š” ์—†์„ ๊ฒƒ ๊ฐ™๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๊ณ , ๊ทธ๋ž˜ํ”ฝ์Šค ๋ Œ๋”๋ง์—์„œ ์‚ฌ์šฉ๋˜๋Š” ๋”๋ธ” ๋ฒ„ํผ๋ง(Double Buffering) ๊ธฐ๋ฒ•์—์„œ ์•„์ด๋””์–ด๋ฅผ ์–ป์–ด, ์œ„์™€ ๊ฐ™์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌ์„ฑํ•˜๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

 

โœ๏ธ์†Œ์Šค ์ฝ”๋“œ ๋ฐ ๊ฒฐ๊ณผ

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000000;
const int DIGIT_COUNT = 10;
const int BUFFER_COUNT = 2;

void Swap(int& x, int& y)
{
    int temp = x;
    x = y;
    y = temp;
}

int main()
{
    ios::sync_with_stdio(false);
    cout.tie(NULL); cin.tie(NULL);

    int N;
    cin >> N;

    // 1. ์ดˆ๊ธฐํ™”
    vector<vector<int>> dp(BUFFER_COUNT, vector<int>(DIGIT_COUNT));
    int writeBufferIndex = 0, readBufferIndex = 1;
    int sum = 9;

    for (int i = 1; i < DIGIT_COUNT; i++)
        dp[writeBufferIndex][i] = 1;
    // ------------------------------------

    // 2. ๋กœ์ง
    Swap(writeBufferIndex, readBufferIndex);
    for (int i = 1; i < N; i++)
    {
        sum = 0;

        for (int j = 0; j < DIGIT_COUNT; j++)
        {
            if (j == 0 or j == 9)
            {
                int targetIndex = (j == 0) ? j + 1 : j - 1;
                int newValue = dp[readBufferIndex][targetIndex];

                dp[writeBufferIndex][j] = newValue;
                sum = (sum + newValue) % MOD;
                continue;
            }

            dp[writeBufferIndex][j] = (dp[readBufferIndex][j - 1] + dp[readBufferIndex][j + 1]) % MOD;
            sum = (sum + dp[writeBufferIndex][j]) % MOD;
        }

        Swap(writeBufferIndex, readBufferIndex);
    }

    cout << sum;
    return 0;
}

 

728x90
๋ฐ˜์‘ํ˜•