취미로 코딩하기

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

이번에 볼 문제는 백준 1094번 문제인 막대기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1094

이 문제는 주어진 정수의 이진수를 생각하면 간단히 풀 수 있다.

문제에서 구하는 수는 주어진 수를 이진수로 표현했을 때 1의 개수와 같다는 것을 쉽게 알 수 있기 때문이다.

이를 바탕으로 구현하면 코드를 간단히 작성할 수 있다.

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

#include <iostream>
using std::cin; using std::cout;
int main()
{
    int x = 0, ans = 0;
    cin >> x;
    while (x > 0) {
        if (x & 1) ans += 1;
        x >>= 1;
    }
    cout << ans;
    return 0;
}

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

이번에 볼 문제는 백준 1476번 문제인 날짜 계산이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1476

이 문제는 어떤 자연수 x를 15로 나눈 나머지가 E-1, 28로 나눈 나머지가 S-1, 19로 나눈 나머지가 M-1일 때 x+1이 무엇인지 구하는 문제와 같다.

15, 28, 19는 모두 서로소이므로, 세 순서쌍에서 x가 1 증가하기 위해 더해야하는 수 6916, y가 1 증가하기 위해 더해야하는 수 4845, z가 1 증가하기 위해 더해야하는 수 4200을 구해 주어지는 E, S, M값에서 1을 빼 곱해 더한 값을 구하자.

이 값을 15*28*19 = 7980으로 나눈 나머지를 구하면 (답-1)을 알 수 있다.

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

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

int main()
{
    int x, y, z; cin >> x >> y >> z;
    cout << ((x - 1) * 6916 + (y - 1) * 4845 + (z - 1) * 4200) % 7980 +1;
    return 0;
}

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

이번에 볼 문제는 백준 12728번 문제인 n제곱 계산이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/12728

이 문제에서 주의해야할 점은 단순히 거듭제곱만 하면 지수가 커질 수록 실수부에서 오차가 크게 발생하게 된다는 것이다. 따라서, 단순히 빠르게 계산하는 것만 고려할 것이 아닌 실수오차가 나지 않게 정수만으로 해결할 방법을 찾는 것이 좋다.

문제집에 종종 나오는 문제풀이 트릭을 떠올려보자.

3-sqrt(5)<1 을 만족하는 것은 분명하고, X = (3+sqrt(5))^n + (3-sqrt(5))^n 이 정수임을 보이는 것은 이항정리(binomial theorem)을 이용하면 간단히 보일 수 있다.

따라서 (3+sqrt(5))^n의 정수값은 X에서 1을 뺀 값임을 알 수 있다.

또한, (3+sqrt(5))^n을 a+b*sqrt(5) 로 표현할 때, X = 2*a임도 알 수 있다.

따라서 남은 것은 (3+sqrt(5))^n = a+b*sqrt(5)를 만족하는 a와 b를 빠르게 찾는 것이다.

이는 관계식을 행렬로 작성한 뒤 binary exponentiation을 이용하면 빠르게 해결 가능하다.

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

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

int main()
{
    int T; cin >> T;
    long long N;
    for (int t = 1;t <= T;t++) {
        cin >> N;
        int mat[2][2] = { {3,5},{1,3} };
        int res[2] = { 1,0 };
        while (N > 0) {
            if (N & 1) {
                int temp[2] = { mat[0][0] * res[0] + mat[0][1] * res[1],mat[1][0] * res[0] + mat[1][1] * res[1] };
                res[0] = temp[0] % 1000; res[1] = temp[1] % 1000;
            }
            int temp[2][2] = { {mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0],mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1]},
                {mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0],mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1]} };
            mat[0][0] = temp[0][0] % 1000; mat[0][1] = temp[0][1] % 1000; mat[1][0] = temp[1][0] % 1000; mat[1][1] = temp[1][1] % 1000;
            N >>= 1;
        }
        int ans = (res[0] * 2 - 1)%1000;
        if (ans < 10) {
            cout << "Case #" << t << ": 00" << ans << '\n';
        }
        else if (ans < 100) {
            cout << "Case #" << t << ": 0" << ans << '\n';
        }
        else {
            cout << "Case #" << t << ": " << ans << '\n';
        }
    }
    return 0;
}

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

이번에 볼 문제는 백준 2294번 문제인 동전 2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2294

이 문제는 주어진 액수의 동전을 개수 제한없이 최대한 적은 개수로 사용하여 목표 금액을 만들어야 한다.

이를 위해, 각 동전이 들어올 때마다 목표금액 이하의 금액들에 대하여 만들 수 있는 최소 동전 개수를 계속 갱신해나가면 문제를 해결할 수 있다.

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

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

int total[10001];

int main()
{
    int N, K; cin >> N >> K;
    int coin, index;
    for (int i = 0;i < N;i++) {
        cin >> coin; index = 0;
        while (index + coin <= K) {
            if (total[index] != 0 or index == 0) {
                if (total[index + coin] == 0) total[index + coin] = total[index] + 1;
                else total[index + coin] = min(total[index] + 1, total[index + coin]);
            }
            index++;
        }
    }
    if (total[K] == 0) total[K] = -1;
    cout << total[K];

    return 0;
}

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

이번에 볼 문제는 백준 11048번 문제인 이동하기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11048

이 문제에서는 미로의 칸을 위에서 아래 행 방향으로, 같은 행이라면 왼쪽에서 오른쪽 열 방향으로 둘러보면서 이 칸으로 진입할 때 왼쪽에서 진입하는 것과 위쪽에서 진입하는 것중 어떤 경우에 더 많은 사탕을 얻는지 살펴 기록해나가는 것으로 풀 수 있다.

대각선 방향의 이동은 따로 고려할 필요가 없는데, 가장 많은 사탕을 줍는 경로 중 최단거리까지 구하는 것을 문제가 요구하고 있지 않기 때문이다.

대각선 방향의 이동이 포함된 경로가 가장 많은 사탕을 줍는 경로라면, 그 대각선 경로 대신 아래방향 한칸 이동과 오른쪽방향 한칸 이동을 대신 해도 기존 경로에 있는 사탕을 모두 주으므로 오른쪽방향 이동과 아래방향 이동만 고려해도 상관이 없다.

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

#include <iostream>
#include <cmath>
using std::cin; using std::cout;
using std::max;
int arr[1001][1001];

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

    int row, column; cin >> row >> column;

    int x;

    for (int i = 1;i <= row;i++) {
        for (int j = 1;j <= column;j++) {
            cin >> x; arr[i][j] = x;
            arr[i][j] += max(arr[i-1][j], arr[i][j-1]);
        }
    }
    cout << arr[row][column];

    return 0;
}

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

이번에 볼 문제는 백준 1991번 문제인 트리 순회이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11055

이 문제는 증가 부분 수열 가운데 각 항의 총합이 가장 큰 부분 수열을 찾는 문제이다.

수열을 구성하는 수는 모두 1000 이하의 양의 정수이므로, 크기 1000짜리 배열을 만들어 숫자가 들어올 때마다 배열의 해당 숫자번째 원소를 그 수로 끝나는 부분수열 중 합이 최대인 경우로 갱신해나가주면 문제를 해결할 수 있다.

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

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

int nums[1001];

int main()
{
    int N; cin >> N;
    int x;
    for (int _ = 0;_ < N;_++) {
        cin >> x;
        if (nums[x] < x) nums[x] = x;
        for (int i = x - 1; i >= 0;i--) {
            if (nums[i] + x > nums[x]) nums[x] = nums[i] + x;
        }
    }
    int ans = 0;
    for (int i = 0;i <= 1000;i++) {
        if (ans < nums[i]) ans = nums[i];
    }
    cout << ans;

    return 0;
}