여러분들의 열화[?]와 같은 성원에 힘입어 알고스팟 에디토리얼에도 올리는 스탱입니다.

A. Alien Language
외계어는 L개의 소문자로 이루어진 단어 D개가 있다. N개의 패턴이 주어졌을 때, 각각의 패턴에 해당하는 단어가 몇개씩 있는지 구하는 프로그램을 작성하시오. 패턴의 각 글자는 소문자거나 괄호로 둘러쌓여진 소문자들의 그룹으로 이루어져 있다. 예를 들어 (ab)d(dc) 같은 경우, 첫 글자는 a 또는 b, 두번째 글자는 d, 세번째 글자는 d 또는 c인 단어를 의미하며, add, adc, bdd, bdc 의 4가지 가능성이 있다.
[spoiler="더 보기..."]
간단한 패턴 매칭 문제입니다. 괄호 처리만 잘 해주면 특별히 코딩에 어려운 부분은 없습니다.
~~~ cpp

#include
#include
#include
#include
using namespace std;
int check(string a, string b)
{
int pos = 0;
for (int i = 0; i < b.size(); ++i)
{
string word = "";
if (a[pos] == '(')
{
for (int j = pos + 1; ; ++j)
if (a[j] == ')')
{
pos = j + 1;
break;
}
else word += a[j];
}
else
{
word = a[pos];
pos++;
}
bool isOK = false;
for (int j = 0; j < word.size(); ++j)
if (word[j] == b[i]) isOK = true;
if (!isOK) return 0;
}
if (pos != a.size()) return 0;
return 1;
}
int main()
{
int L, D, N;
cin >> L >> D >> N;
vector word(D);
for (int i = 0; i < D; ++i)
cin >> word[i];
for (int q = 0; q < N; ++q)
{
int ret = 0;
string str;
cin >> str;
for (int i = 0; i < D; ++i)
{
if (check(str, word[i])) ret++;
}
printf("Case #%d: %dn", q + 1, ret);
}
}

[/spoiler]


B. Watersheds
  높이가 표시된 지도가 있다. 어떤 위치에 비가 오는 경우, 빗물은 특정한 조건에 따라 흐른다.
  1. 각 칸에서 빗물은 인접한 4개의 칸으로만 흐른다
  2. 각각의 칸에 대해서, 현재 위치보다 낮은 곳이 주변에 없는 경우, 물은 흐르지 않고, 현재의 칸은 sink가된다.
  3. 그렇지 않으면 물은 인접한 칸들 중 제일 낮은 칸으로 흐른다.
  4. 만약 3번의 경우, 제일 낮은 높이의 인접한 칸이 여러 개 있는 경우, N, W, E, S의 순서대로 흐른다.
  모든 칸의 물은 직접 혹은 간접적으로 흐르게 되고, 이는 sink에서 모이게 된다. 동일한 sink에 모이는 지점들을 하나의 그룹으로
묶는다고 할 때, 그룹들을 알파벳으로 구분해 보자.
[spoiler="더 보기..."]
  주어진 지도에서 물이 어느 방향으로 흐르는지를 그래프로 나타낼 수 있습니다. 이 그래프에서 어떤 sink로 도달하는지를 찾아서 같은 sink끼리 묶어주면 됩니다. 저는 어떤 칸에서 물이 흐른다면 이를 무방향성 그래프로 만들어서 같은 그룹을 묶는 방식으로 해결하였습니다.
~~~ cpp

#include <iostream>
#include <queue>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
int table[101][101];
vector< int > graph[101][101];
char ret[101][101];
char ch;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
void go(int x, int y)
{
    queue<pair<int, int> > Q;
    Q.push( make_pair( x, y ));
    ret[x][y] = ch;
    while (!Q.empty())
    {
        pair<int, int> now = Q.front(); Q.pop();
        x = now.first, y = now.second;
        for (int i = 0; i < graph[x][y].size(); ++i)
        {
            int nx = x + dx[ graph[x][y][i] ];
            int ny = y + dy[ graph[x][y][i] ];
            if (ret[nx][ny] == '?') 
            {
                ret[nx][ny] = ch;
                Q.push(make_pair( nx, ny ));
            }
        }
    }
}
int main()
{
    int T;
    cin >> T;
    int n, m;
    for (int q = 1; q <= T; ++q)
    {
        cin >> n >> m;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                cin >> table[i][j];
                graph[i][j].clear();
                ret[i][j] = '?';
            }
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                bool isSink = true;
                int mn = table[i][j];
                int p = -1;
                for (int k = 0; k < 4; ++k)
                {
                    int nx = i + dx[k], ny = j + dy[k];
                    if (nx < 0 || nx == n || ny < 0 || ny == m) continue;
                    if (table[i][j] > table[nx][ny]) isSink = false;
                    if (mn > table[nx][ny])
                    {
                        mn = table[nx][ny];
                        p = k;
                    }
                }
                if (isSink) continue;
                graph[i][j].push_back( p );
                graph[i + dx[p]][j + dy[p]].push_back( 3 - p );
            }
        }
        ch = 'a';
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if( ret[i][j] == '?' ) 
                {
                    go(i, j);
                    ch++;
                }
            }
        }
        cout << "Case #" << q << ":" << endl;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
                cout << ret[i][j] << ' ';
            cout << endl;
        }
    }
    return 0;
}

[/spoiler]

C. Welcome to Code Jam
주어진 string에서 "welcome to code jam"을 만들 수 있는 조합의 경우의 수를 출력하여라. 단 10000으로 나눈 나머지를 구하시오
[spoiler="더 보기..."]
전형적인 DP 문제입니다... 10000으로 나눈 나머지는 고등학교때 배우는 나머지 정리[ (A + B) % C = ((A % C) + (B % C)) % C
] 를 이용하시면 구할 수 있습니다.
~~~ cpp

#include
#include
#include
using namespace std;
int T;
string s = "welcome to code jam";
int table[505][25];
int main()
{
string str;
char tmp[1005];
fgets(tmp, 1000, stdin); str = tmp;
istringstream sin(str); sin >> T;
for (int Q = 1; Q <= T; ++Q)
{
fgets(tmp, 1000, stdin); str = tmp;
memset(table, 0, sizeof(table));
for (int i = 0; i < str.size(); ++i)
{
for (int j = 0; j < s.size(); ++j)
{
if (i != 0) table[i][j] = table[i - 1][j];
if (str[i] == s[j])
{
if (j == 0) table[i][j]++;
else if (i > 0) table[i][j] += table[i - 1][j - 1];
}
table[i][j] %= 10000;
}
}
printf("Case #%d: %04dn", Q, table[str.size() - 1][s.size() - 1]);
}
}

[/spoiler]




<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/60555">원문보기</a>]</div>