취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 20493번 문제인 세상은 하나의 손수건이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/20493

이 문제는 주어진 입력을 받아 순서대로 이어서 처리하는 문제이다.

문제에서 시키는 대로 하면 금방 풀 수 있다.

함수를 정의하면 더 간단히 풀 수 있었을 것 같은 아쉬움이 남는다.

#include <iostream>
#include <string>
using std::string;
using std::cin;
using std::cout;

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int x = 0, y = 0, timebefore = 0;
    int N, T;
    cin >> N >> T;
    int temp_T;
    int dir=0; // 0: x방향 , 1: y방향, 2: -x방향, 3: -y방향
    string temp_dir;
    for (int i = 0;i < N;i++) {
        cin >> temp_T >> temp_dir;
        if (dir == 0) {
            x += (temp_T - timebefore);
        }
        else if (dir == 1) {
            y += (temp_T - timebefore);
        }
        else if (dir == 2) {
            x -= (temp_T - timebefore);
        }
        else y -= (temp_T - timebefore);

        timebefore = temp_T;

        if (temp_dir == "right") {
            dir = (dir - 1) % 4;
            if (dir < 0) dir += 4;
        }
        else dir = (dir + 1) % 4;
    }
    // 마지막 움직임
    if (dir == 0) {
        x += (T - timebefore);
    }
    else if (dir == 1) {
        y += (T - timebefore);
    }
    else if (dir == 2) {
        x -= (T - timebefore);
    }
    else y -= (T - timebefore);

    cout << x <<' '<< y;

    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15610번 문제인 Abbey Courtyard이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/6603

이 문제는 오름차순으로 주어진 숫자들 가운데 6개의 수를 고르는 경우의 수를 빠짐없이 나열하는 문제이다.

모든 경우를 나열해야하므로 가능한 모든 경우를 일일이 탐색하자.

recursion을 이용하면 간단히 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::vector;
using std::cin;
using std::cout;

int S[12];
bool visited[12];
vector<int> comb;
vector<int>::iterator iter;

void func(int x, int y) {
    if (comb.size() == 6) {
        for (iter = comb.begin();iter != comb.end();iter++) {
            cout << S[*iter] << ' ';
        }
        cout << '\n';
    }
    else {
        for (int i = y;i < x;i++) {
            if (!visited[i]) {
                visited[i] = true;
                comb.push_back(i);
                func(x,i+1);
                comb.pop_back();
                visited[i] = false;
            }
        }
    }
}

int main()
{
    int x;
    cin >> x;
    int y;
    while (x != 0) {
        for (int i = 0;i < x;i++) {
            cin >> y;
            S[i] = y;
        }
        func(x,0);
        cout << '\n';
        cin >> x;
    }
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15610번 문제인 Abbey Courtyard이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/15610

이 문제는 주어진 long long인 정수 넓이의 정사각형 의 둘레의 길이를 구하는 문제이다.

계산에 제곱근이 들어가고, relative error(상대오차)가 최대 10^(-6)이여야한다는 점을 확인하고 풀자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
#include <iomanip>
using std::sqrt;
using std::cin;
using std::cout;
using std::setprecision;

int main()
{
	double n;
	cin >> n;
	cout << setprecision(20) << 4*sqrt(n);

	return 0;
}

www.acmicpc.net/problem/1533

이 문제는 S에서 출발하여 T분 뒤에 E에 도착하는 경우의 수를 구하는 문제이다.

여기서 이 그래프의 각 간선에 가중치가 0~5까지 설정되어있으므로 그 경우를 나눠서 계산하자.

다음은 이 문제를 풀기 위한 행렬 mat을 block matrix로 표현한 것이다. 각 block은 N by N 행렬이다.

이 행렬을 곱할 벡터 vec의 초기값은 다음과 같다. 각 block의 성분은 N개이다.

이렇게 설정하면 mat의 T제곱을 vec에 곱해 나온 첫 블럭은 점 S에서 출발해 점 1~N까지 도달하는 경우의 수를 담게 된다. mat의 T제곱은 binary exponentiation을 통해 빠르게 계산할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;

long long mat[60][50];
long long tempmat[50][50];
long long vec[50];
long long tempvec[50];

int main()
{
    int N, S, E, T;
    cin >> N >> S >> E >> T;
    vec[S - 1] = 1; // 시작점 초기값 1, 나머지 0
    string x;
    for (int i = 0;i < N;i++) {
        cin >> x;
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 1인 성분들
            if (x[j] == '1') {
                mat[j][i] = 1;
            }
        }
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 2인 성분들
            if (x[j] == '2') {
                mat[j][i + N] = 1;
            }
        }
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 3인 성분들
            if (x[j] == '3') {
                mat[j][i + 2 * N] = 1;
            }
        }
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 4인 성분들
            if (x[j] == '4') {
                mat[j][i + 3 * N] = 1;
            }
        }
        for (int j = 0;j < N;j++) { // adjacency matrix의 transpose에서 5인 성분들
            if (x[j] == '5') {
                mat[j][i + 4 * N] = 1;
            }
        }
    }
    for (int i = 0;i < 5 * N;i++) { // 지나간 네 개의 경우를 아래로 옮김
        mat[i + N][i] = 1;
    }

    while (T > 0) { // binary exponentiation
        if (T & 1) {
            for (int i = 0; i < 5 * N; i++) {
                for (int k = 0; k < 5 * N; k++) {
                    tempvec[i] += mat[i][k] * vec[k];
                }
            }
            for (int i = 0; i < 5 * N; i++) {
                vec[i] = tempvec[i] % 1000003;
                tempvec[i] = 0;
            }
        }

        for (int i = 0; i < 5 * N; i++) {
            for (int j = 0; j < 5 * N; j++) {
                for (int k = 0;k < 5 * N;k++) {
                    tempmat[i][j] += mat[i][k] * mat[k][j];
                }
            }
        }
        for (int i = 0; i < 5 * N; i++) {
            for (int j = 0; j < 5 * N; j++) {
                mat[i][j] = tempmat[i][j] % 1000003;
                tempmat[i][j] = 0;
            }
        }

        T >>= 1;
    }

    cout << vec[E - 1]; // E번 노드까지 가는 경로의 수

    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13328번 문제인 Message Passing이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/13328

이 문제에서 맨 처음 연락을 돌리는 Kim씨를 제외하면 모든 사람들은 1분 간격으로 d번 연락을 한다. 즉, 어떤 x분 시점에서 연락을 받는 사람들은 x-1, x-2, x-3, ... , x-d 분 전에 연락을 받은 사람이 돌린 통화라고 해석할 수 있다. 이 점화관계를 행렬로 나타내서 binary exponentiation을 이용하면 문제를 해결할 수 있다.

다음은 이해를 돕기 위한 단순한 예시이다.

[ 1 1 1 1 1 ] [ a_7 ]    [ a_8 ]

[ 1 0 0 0 0 ] [ a_6 ]    [ a_7 ]

[ 0 1 0 0 0 ] [ a_5 ] = [ a_6 ]

[ 0 0 1 0 0 ] [ a_4 ]    [ a_5 ]

[ 0 0 0 1 0 ] [ a_3 ]    [ a_4 ]

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

long long mat[51][50];
long long mtt[50][50];
long long vec[50];
long long tmp[50];

int main()
{
    vec[0] = 1; // vec = { a_0, 0, 0, ..., 0 }

    int d, t;
    cin >> d >> t;
    for (int i = 0;i < d;i++) { // 문제에 주어진 점화관계를 d by d 행렬로 나타내기
        mat[0][i] = 1;
        mat[i + 1][i] = 1;
    }
    while (t > 0) { // 위에서 만든 행렬의 t제곱을 vec에 곱하면 { a_t, a_(t-1), ... , a_(t-d+1) } 가 된다.
        if (t & 1) { // binary exponentiation
            for (int i = 0;i < d;i++) {
                for (int j = 0;j < d;j++) {
                    tmp[i] += mat[i][j] * vec[j];
                }
            }
            for (int j = 0;j < d;j++) {
                vec[j] = tmp[j]%31991;
                tmp[j] = 0;
            }
        }
        for (int i = 0; i < d; i++) {
            for (int j = 0;j < d;j++) {
                for (int k = 0;k < d;k++) {
                    mtt[i][j] += mat[i][k] * mat[k][j];
                }
            }
        }
        for (int i = 0; i < d; i++) {
            for (int j = 0;j < d;j++) {
                mat[i][j] = mtt[i][j]%31991;
                mtt[i][j] = 0;
            }
        }
        t >>= 1;
    }
    cout << vec[0];

    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14470번 문제인 전자레인지이다.

문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/12850

산책시간이 더 적게 제약이 걸린 다음 문제도 있다.

www.acmicpc.net/problem/12849

이 문제는 주어진 캠퍼스지도를 그래프로 생각하고 adjacency matrix(인접행렬)을 만들어 그 성질을 이용하는 것으로 풀 수 있다. adjacency matrix를 n제곱한 행렬의 i행 j열 성분은 node i에서 j로 가는 길이 n짜리 경로의 개수이다.

일반적으로 adjacency matrix는 그래프를 표현할 때 없는 edge에 대한 정보까지 0이라는 숫자로 기록하기 때문에 많은 문제에서 효율적이지 못한 자료 저장방법이지만, node의 수가 충분히 적을 때 node i에서 j로 가는 주어진 길이의 경로의 수를 구하는 데에는 쓰기 매우 좋다. 행렬은 binary exponentiation을 통해 빠르게 거듭제곱을 구할 수 있기 때문이다.

따라서 이 문제를 푸는 과정은 다음과 같다.

1) 지도를 그래프로 보고 adjacency matrix를 만든다.

글쓴이는 문제의 지도에서 정보과학관을 0, 전산관을 1, 미래관을 2, 신양관을 3, 한경직기념관을 4, 진리관을 5, 형남공학관을 6, 학생회관을 7로 잡고 adjacency matrix를 만들었다.

2) binary exponentiation으로 adjacency matrix의 D(문제에서 주어진 산책시간) 제곱을 구한다.

3) 구하는 산책경로는 정보과학관에서 정보과학관으로 가는 경로이므로 거듭제곱한 행렬의 0행0열 성분을 답으로 출력한다.

다음은 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

// mat: adjacency matrix, ans: identity matrix, tmp: 계산과정 중간저장용
long long mat[8][8] = { {0,1,1,0,0,0,0,0},{1,0,1,1,0,0,0,0},{1,1,0,1,1,0,0,0},{0,1,1,0,1,1,0,0},{0,0,1,1,0,1,1,0},{0,0,0,1,1,0,0,1},{0,0,0,0,1,0,0,1},{0,0,0,0,0,1,1,0} };
long long ans[8][8] = { {1,0,0,0,0,0,0,0},{0,1,0,0,0,0,0,0},{0,0,1,0,0,0,0,0},{0,0,0,1,0,0,0,0},{0,0,0,0,1,0,0,0},{0,0,0,0,0,1,0,0},{0,0,0,0,0,0,1,0},{0,0,0,0,0,0,0,1} };
long long tmp[8][8];
int main()
{
    int D;
    cin >> D;
    while (D > 0) { // binary exponentiation
        if (D & 1) {
            for (int i = 0;i < 8; i++) {
                for (int j = 0;j < 8;j++) {
                    for (int k = 0;k < 8;k++) {
                        tmp[i][j] += mat[i][k] * ans[k][j];
                    }
                }
            }
            for (int i = 0;i < 8; i++) {
                for (int j = 0;j < 8;j++) {
                    ans[i][j] = tmp[i][j]%1000000007;
                    tmp[i][j] = 0;
                }
            }
        }
        for (int i = 0;i < 8; i++) {
            for (int j = 0;j < 8;j++) {
                for (int k = 0;k < 8;k++) {
                    tmp[i][j] += mat[i][k] * mat[k][j];
                }
            }
        }
        for (int i = 0;i < 8; i++) {
            for (int j = 0;j < 8;j++) {
                mat[i][j] = tmp[i][j] % 1000000007;
                tmp[i][j] = 0;
            }
        }
        D >>= 1;
    }
    cout << ans[0][0];

    return 0;
}