취미로 코딩하기

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

이번에 볼 문제는 백준 9465번 문제인 스티커이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/9465

이 문제는 간단한 점화식으로 풀 수 있는 문제이다.

왼쪽에서부터 k번째 칸까지의 점수가 가장 크게 스티커를 잘라내는 케이스를 생각해보자.

k-1번째 칸의 위아래 스티커를 (안 가져갈 수는 있지만) 모두 가져갈 수는 없으므로(문제 조건), k번째 칸에서 스티커를 잘라내지 않고 최댓값을 얻을 수는 없다.

그렇다면 점수가 최대가 되게 스티커를 잘라내는 경우는 k번째 스티커 중 윗칸 스티커를 잘라내면서 최대인 경우, 아랫칸 스티커를 잘라내면서 최대인 경우 두가지중 하나가 된다.

윗칸 스티커를 잘라낼 거라면, 이전 칸의 아랫칸 스티커를 잘라냈거나 이전 칸의 스티커를 가져오지 않아야한다.

아랫칸 스티커를 잘라낼거라면, 이전 칸의 윗칸 스티커를 잘라냈거나 이전 칸의 스티커를 가져오지 않아야한다.

이를 식으로 나타내면 다음과 같다.

(윗칸 스티커 자르는 점수 최댓값)

= max( (전칸 아랫칸까지 점수 최댓값), (전전칸까지 점수 최댓값) ) + 윗칸 스티커 점수

(아랫칸 스티커 자르는 점수 최댓값)

= max( (전칸 윗칸까지 점수 최댓값), (전전칸까지 점수 최댓값) ) + 아랫칸 스티커 점수

이것을 맨 왼쪽 칸에서부터 순서대로 계산해나가면 원하는 결과를 얻을 수 있다.

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

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

int A[100000]; // 윗칸 스티커
int B[100000]; // 아랫칸 스티커

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

    int T; // 테스트 케이스 수
    cin >> T;

    int a, b;
    int n;
    int x;
    for (int i = 0;i < T;i++) {
        cin >> n; // 스티커 입력받기
        for (int j = 0;j < n;j++) {
            cin >> x;
            A[j] = x;
        }
        for (int j = 0;j < n;j++) {
            cin >> x;
            B[j] = x;
        }
        a = 0; // 초기화
        b = 0;
        x = 0;
        for (int j = 0;j < n;j++) {
            int tempa = max(b, x) + A[j]; // 다음 윗스티커 최댓값 계산
            int tempb = max(a, x) + B[j]; // 다음 아랫스티커 최댓값 계산
            x = max(a, b); // 다음 계산에 쓸 이번칸 비운 최댓값
            a = tempa; b = tempb;
        }
        cout << max(a, b) << '\n';
    }
}

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

이번에 볼 문제는 백준 1300번 문제인 K번째 수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1300

문제는 단순하다. index가 1부터 시작하는 N×N 배열의 성분을 각 index의 곱으로 하고, 이 배열의 각 값들을 (중복을 허용하여) 오름차순으로 정렬할 때 k번째 수가 무엇일지 계산하는 것이다.

N이 10만까지 가능하기 때문에 직접 모든 값을 계산하여 정렬하는 방식으로는 제한시간 내로 당연히 풀 수 없을 것이다.

이 문제를 푸는 요령은 다음과 같다.

다음과 같은 문제를 생각하자:

주어진 N×N 배열에 양의 정수 x 이하인 원소는 몇 개가 있는가?

이 문제는 수학적 지식을 이용하면 단순하게 풀 수 있다. 자명하게, x가 커지면 N×N의 x 이하 양의 정수의 개수는 같거나 증가한다. 따라서 위 문제를 푸는 함수와 binary search를 이용하여 x 이하의 양의 정수의 개수가 (원래 문제에서 주어진) k개 이하인 정수 중 가장 작은(그보다 큰 수는 배열에 없는 수) 수를 찾으면 된다.

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

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

int counting(int n,int k) { // "작은 문제"를 푸는 함수
    int cnt = 0;
    for (int i = 1;i < n + 1;i++) {
        cnt += min(k / i, n);
    }
    return cnt;
}

int main()
{
    int n, k;
    cin >> n >> k;
    int left = 1, right = k; // n의 제곱으로 해도 되지만 k가 더 작다
    while (left <= right) { // binary search 시작
        int mid = (left + right) / 2;
        int count = counting(n, mid);
        if (count >= k) right = mid - 1; // 양의 정수 mid 이하의 원소개수가 k보다 많거나 같다면 숫자가 더 작은 쪽 범위를 탐색
        else left = mid + 1; // 양의 정수 mid 이하의 원소개수가 k보다 적다면 숫자가 더 큰 쪽 범위를 탐색
    } 
    // left==right의 상황에서 right가 정답보다 1 작은 수라면 left도 정답보다 1 작은 수이고,
    // 마지막에 left가 +1되므로 left는 정답을 가리킨다.
    // left==right의 상황에서 right가 정답을 가리킨다면 left도 정답을 가리키고,
    // 마지막에 right의 값이 -1이 되므로 left는 정답을 가리킨다.
    cout << left;
    
    return 0;
}

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

이번에 볼 문제는 백준 1253번 문제인 좋다이다.

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

www.acmicpc.net/problem/1253

이 문제는 2-sum problem 의 변형으로 볼 수 있다.

2-sum problem은 정수의 배열 arr과 어떤 수 target이 주어졌을 때 그 수를 배열의 (distinct한) 두 index에 있는 수의 합으로 나타낼수 있는지를 묻는 문제이다. 2-sum problem은 대표적인 투포인터 문제로, 자세한 내용은 나중에 따로 다루겠다.

이 문제를 풀 때 유의해야할 점은 target을 배열에서 뽑아왔다는 것이다. 즉, 합하는 두 수의 index는 target과도 달라야한다. 예를 들어, 0 0 2 2 라는 배열을 살펴보자. 두 2는 다른 index에 있는 2와 0 하나의 합으로 표현이 가능하니 좋다(GOOD)고 할 수 있다. 하지만 두 0은 자기자신을 제외한 두 수의 합으로 0을 만들 수 없다. (자기 자신을 포함한다면 가능하다.) 글쓴이는 이 문제를 포인터 중 하나가 target을 가리킨다면 다음 index로 넘기는 방식으로 해결했다.

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

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

int nums[2000];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; // 배열 읽어오기
    int x;
    cin >> n;
    for (int i = 0;i < n;i++) {
        cin >> x;
        nums[i] = x;
    }
    sort(nums, nums + n); // 배열 정렬하기
    int ans = 0; // ans: 다른 두 수의 합으로 나타낼 수 있는 수의 개수
    for (int i = 0;i < n;i++) { // 각 수(nums[i])에 대한 반복문
        int target = nums[i];
        int leftpt = 0; // 포인터 정의
        if (leftpt == i) leftpt++; // 예외처리 - 합으로 나타내려는 수와 겹치는 index
        int rightpt = n - 1;
        if (rightpt == i) rightpt--;
        while (rightpt > leftpt) { // 투 포인터 구현
            int currentsum = nums[leftpt] + nums[rightpt];
            if (currentsum == target) {
                ans++;
                break;
            }
            else if (currentsum > target) {
                rightpt--;
                if (rightpt == i) rightpt--; // 예외처리 - 합으로 나타내려는 수와 겹치는 index
            }
            else {
                leftpt++;
                if (leftpt == i) leftpt++;
            }
        }
    }
    cout << ans;
    
    return 0;
}

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

이번에 볼 문제는 백준 1744번 문제인 수 묶기이다.

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

www.acmicpc.net/problem/1744

이 문제는 주어진 숫자를 둘씩 짝을 지어 곱해 더하거나 그냥 더해 최댓값을 얻는 것이 목표이다.

이때, 주어지는 숫자에는 양수도 음수도 있음에 유의하여야 한다.

이 문제의 풀이를 구상할 때 신경써야하는 점을 살펴보자.

1) 두 음의 정수의 곱은 양의 정수가 된다. 따라서 음의 정수가 여러 개 있다면 가장 작은(절댓값이 가장 큰) 두 수를 곱해 더해줘야한다.

2) 위와 같이 묶고 음의 정수가 1개 남았을 때 남은 정수 중 0이 있다면 음의 정수를 더하는 것보다는 음수와 0을 곱해 더해야 한다. 남는 0이 있다면 그냥 더해주면 된다. (음의 정수끼리 곱하여 양수를 만드는 것이 더 이득이기 때문)

3) 양의 정수들은 큰 수 2개끼리 묶어서 곱해나가야한다. 단, 1은 다른 수와 곱하지 말고 따로 더해야 한다.

위 내용을 신경쓰면서 다음과 같은 알고리즘을 구상하였다.

1) 입력을 받아 배열을 만든 후 크기순으로 정렬한다.

2) 배열의 왼쪽서부터 양이 아닌 정수를 크기순으로, 짝을 지을 수 없을 때까지 둘씩 묶어 곱해 더한다.

2-1) 짝을 짓지 못하고 남은 수는 그냥 더해준다.

3) 배열의 오른쪽서부터 1보다 큰 양의 정수를 크기순으로, 짝을 지을 수 없을 때까지 둘씩 묶어 곱해 더한다.

3-1) 짝을 짓지 못하고 남은 수는 그냥 더해준다.

4) 남은 수는 1 뿐이다. 1의 개수를 더해준다.

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

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

int nums[10000];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    int x;
    int cntone = 0;
    for (int i = 0;i < n;i++) {
        cin >> x;
        nums[i] = x;
        if (x == 1) cntone++; // 1의 개수를 미리 세둔다
    }
    sort(nums, nums + n);
    int ans = 0;
    int leftpt = 0; // 배열의 왼쪽부터 살필 포인터
    int rightpt = n - 1; // 배열의 오른쪽부터 살필 포인터
    if (n == 1) cout << nums[0]; // 예외처리 -  배열의 크기가 1인 경우
    else {
        while (nums[leftpt + 1] < 1) { // 양이 아닌 정수들을 크기순으로 짝지어 곱해 더하기
            ans += nums[leftpt] * nums[leftpt + 1];
            leftpt += 2;
            if (leftpt == n - 1 or leftpt == n) break; // 예외처리 - 배열의 모든 정수가 음수인 경우
        }
        if (leftpt < n) { // 짝을 짓지 못하고 남은 양이 아닌 정수를 더하기
            if (nums[leftpt] < 1) ans += nums[leftpt];
        }
        while (nums[rightpt - 1] > 1) { // 1보다 큰 양의 정수들을 크기순으로 짝지어 곱해 더하기
            ans += nums[rightpt] * nums[rightpt - 1];
            rightpt -= 2;
            if (rightpt == 0 or rightpt == -1) break; // 예외처리 - 배열의 모든 정수가 양수인 경우
        }
        if (rightpt >= 0) { // 짝을 짓지 못하고 남은 1보다 큰 양의 정수를 더하기
            if (nums[rightpt] > 1) ans += nums[rightpt];
        }
        ans += cntone; // 1을 개수만큼 더해주기
        cout << ans;
    }
    
    return 0;
}

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

이번에 볼 문제는 백준 6615번 문제인 콜라츠 추측이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/6615

이 문제에서는 두 숫자 A, B로 Collatz sequence를 만들 때 몇 번째 숫자에서 처음으로 만나는지를 구해야 한다.

두 숫자가 처음으로 같아지는 순간이 오면, 그 이후로 서로 다른 숫자가 나올 수 없으므로

두 Collatz 수열의 뒤부터 앞으로 서로 다른 수가 나올 때까지 한칸씩 이동하여 문제를 풀 수 있다.

주어지는 입력은 100만 이하이지만 수열의 값은 int범위를 넘어설 수 있다는 점에 유의하자.

또한, 위키백과에 따르면, 100만 미만 수로 시작하는 Collatz sequence의 길이의 최댓값은 524이다.

(837799로 시작하는 수열이다.) 따라서 배열의 크기를 지나치게 크게 선언할 필요는 없다.

모든 Collatz sequence는 1로 끝난다는 문제의 가정을 받아들이면(실제로 100만 이하의 범위에서는 성립), 두 Collatz sequence는 모두 1로 끝나므로 이 알고리즘은 잘 작동한다.

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

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

long long arrA[530]; // 1000000 미만에서 나올 수 있는 길이의 최댓값은 524 
long long arrB[530];

int main()
{
    cin.tie(0);

    long long A, B; // A와 B는 int범위를 벗어날 수 있음에 유의
    cin >> A >> B;
    while (A != 0 and B != 0) { //종료 조건
        int originalA = A;
        int originalB = B;
        int pA = 0, pB = 0;
        while (A != 1) { // Collatz sequence of A
            arrA[pA] = A;
            if (A % 2 == 1) A = 3 * A + 1;
            else A = A / 2;
            pA++;
        }
        arrA[pA] = 1;
        while (B != 1) { // Collatz sequence of B
            arrB[pB] = B;
            if (B % 2 == 1) B = 3 * B + 1;
            else B = B / 2;
            pB++;
        }
        arrB[pB] = 1;
        while (arrA[pA] == arrB[pB]) { // 서로 다른 수가 나올 때까지 1부터 거꾸로 탐색
            pA--;
            pB--;
            if (pA == -1 or pB == -1) break;
        }
        int sA = pA + 1;
        int sB = pB + 1;
        long long C = arrA[sA];
        printf("%i needs %i steps, %i needs %i steps, they meet at %lld\n", originalA, sA, originalB, sB, C);
        cin >> A >> B;
    }
}

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

이번에 볼 문제는 백준 5393번 문제인 콜라츠이다.
문제는 아래 링크를 확인하자.

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

www.acmicpc.net/problem/5393

문제 자체는 Collatz's conjecture을 언급하긴 하지만, 이 문제의 풀이와는 관련이 없다.

글쓴이는 이 문제를 3n+1과 관련된 밧줄의 수와 2n과 관련된 밧줄의 수로 구분지어 해결했다.

특히, 3n+1과 관련된 밧줄의 수의 규칙을 찾을 때, 홀수(주기 2)의 개수를 세야 하므로 modulo 6으로 규칙을 찾아준다.

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

#include <iostream>
using std::cin;
using std::cout;
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x; // n은 테스트케이스 수, x는 각 테스트케이스
    cin >> n;
    for (int i = 0;i < n;i++) {
        int ans = 0;
        cin >> x;
        if (x % 2 == 0) ans += x / 2; //2n과 관련된 밧줄의 개수
        else ans += x / 2 + 1;
        if (x % 6 == 0 or x % 6 == 4) ans += x / 3; //3n과 관련된 밧줄의 개수
        else ans += x / 3 + 1;
        cout << ans << '\n';
    }
}