[boj][c++] 1107 리모컨, 14500 테트로미노, 6064 카잉달력

1107 리모컨

문제를 풀기 위해 접근해야 하는 생각이 몇개 있었는데 정리하면

• 숫자 버튼을 누르지 않고 +, - 만 눌렀을 때 걸리는 횟수
• 고장난 버튼을 제외시키는 방법
• 탐색 범위를 정하는 방법

숫자 버튼을 누르지 않고 +, - 만 눌렀을 때 걸리는 횟수

이건 간단하다. 현재 채널 번호에서 n 을 빼면 된다. abs (100 - n) 이라는 식으로 처리할 수 있다.

고장난 버튼을 제외시키는 방법

여기서 막혀서 강의를 참고했다. 강의에서는 이 방법을 bool 배열을 통해 해결했다. 고장난 버튼을 true로 처리해서 다른 연산에서 if문을 활용하는 방법이다.

자료 처리만 잘 해주면 실제 연산은 쉽다.

• 탐색할 수를 10으로 나눈 나머지 값을 bool 배열의 인덱스로 활용한다.
• 탐색할 수를 10으로 나눈다.
• 1과 2 과정을 반복한다.

/*
for (int i = 0; i < m; i++)
    {
        int k;
        cin >> k;
        arr[k] = true;
    }
*/

 while (c > 0)
    {
        if (arr[c % 10])
            return 0;
        c /= 10;
        num++;
    }

이 과정에서 한번이라도 bool 배열의 인덱스가 true를 가키리고 있다면 고장난 버튼이므로 제외시킨다.

탐색 범위를 정하는 방법

이건 사실 고려할 생각도 못했었다. 문제에서 이동하려고 하는 채널의 최대값은 5000000이기 때문에 0부터 500000 까지만 탐색하면 될거라고 생각했다. 그러나 실제로 채널이 500000일 때 절대값을 사용하게 되면 +-를 모두 고려해서 탐색해야 한다.

정확한 수치는 알 수 없으니 시간복잡도가 과하지 않을 정도인 1000000으로 최대값을 정해서 탐색했다.

그 외 자잘자잘한 디테일을 신경써서 코드를 완성하면 된다.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int n, m, now, start, ans;
bool arr[10];

int check(int c)
{
    int num = 0;
    if (c == 0)
    {
        if (arr[0])
            return 0;
        else
            return 1;
    }
    while (c > 0)
    {
        if (arr[c % 10])
            return 0;
        c /= 10;
        num++;
    }
    return num;
}

int main()
{
    now = 100;
    ans = 1000000;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int k;
        cin >> k;
        arr[k] = true;
    }
    ans = min(ans, abs(now - n));
    for (int i = 0; i < 1000000; i++)
    {
        if (check(i))
        {
            int tmp;
            start = check(i);
            tmp = abs(n - i) + start;
            ans = min(ans, tmp);
        }
    }
    cout << ans << endl;
}

14500 테트로미노

이건 문제를 풀기 전에 설계만 잘 하면 구현에서 신경써야 할 부분이 없다.
기본적으로 x와 y의 범위를 넘는 값에 대해서는 예외처리 해야한다. 이건 그래프 문제에서 당연한거니까 생략.

모든 블럭에 대해 놓을 수 있는 블럭의 형태를 모두 구한 뒤 기준점만 잡으면 된다.

위의 그림을 보면 각각의 블럭을 놓을 수 있는 모든 경우의 수는 19가지다. 모든 칸에 대해 19번씩 연산을 수행해야 하는데 n과 m의 최대값은 500이다.

시간 복잡도는 500 ^ 2 * 19. 따라서 완전탐색으로 풀어도 문제없다.

#include <iostream>
#include <algorithm>
using namespace std;

int x, y, n, ans;
int arr[501][501];

int form1(int nx, int ny)
{
    int tmp = 0;
    if (nx + 3 < x)
    {
        tmp = arr[ny][nx] + arr[ny][nx + 1] + arr[ny][nx + 2] + arr[ny][nx + 3];
    }
    if (ny + 3 < y)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny + 1][nx] + arr[ny + 2][nx] + arr[ny + 3][nx]);
    }
    //cout<<"form1's return is "<<tmp<<endl;
    return tmp;
}

int form2(int nx, int ny)
{
    int tmp = 0;
    if (nx + 1 < x && ny + 1 < y)
    {
        tmp = arr[ny][nx] + arr[ny][nx + 1] + arr[ny + 1][nx] + arr[ny + 1][nx + 1];
    }
    //cout<<"form2's return is "<<tmp<<endl;
    return tmp;
}

int form3(int nx, int ny)
{
    int tmp = 0;
    if (nx + 1 < x && ny + 2 < y)
    {
        tmp = arr[ny][nx] + arr[ny + 1][nx] + arr[ny + 2][nx] + arr[ny + 2][nx + 1];
    }
    if (nx - 1 >= 0 && ny + 2 < y)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny + 1][nx] + arr[ny + 2][nx] + arr[ny + 2][nx - 1]);
    }
    if (nx + 1 < x && ny - 2 >= 0)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny - 1][nx] + arr[ny - 2][nx] + arr[ny - 2][nx + 1]);
    }
    if (nx - 1 >= 0 && ny - 2 >= 0)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny - 1][nx] + arr[ny - 2][nx] + arr[ny - 2][nx - 1]);
    }
    if (nx + 2 < x && ny - 1 >= 0)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny][nx + 1] + arr[ny][nx + 2] + arr[ny - 1][nx + 2]);
    }
    if (nx - 2 >= 0 & ny - 1 >= 0)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny][nx - 1] + arr[ny][nx - 2] + arr[ny - 1][nx - 2]);
    }
    if (nx + 2 < x & ny + 1 < y)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny][nx + 1] + arr[ny][nx + 2] + arr[ny + 1][nx + 2]);
    }
    if (nx - 2 >= 0 & ny + 1 < y)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny][nx - 1] + arr[ny][nx - 2] + arr[ny + 1][nx - 2]);
    }
    //cout<<"form3's return is "<<tmp<<endl;
    return tmp;
}

int form4(int nx, int ny)
{
    int tmp = 0;
    if (nx - 1 >= 0 && ny + 1 < y && ny - 1 >= 0)
    {
        tmp = arr[ny][nx] + arr[ny][nx - 1] + arr[ny - 1][nx - 1] + arr[ny + 1][nx];
    }
    if (nx + 1 < x && ny + 1 < y && ny - 1 >= 0)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny][nx + 1] + arr[ny + 1][nx] + arr[ny - 1][nx + 1]);
    }
    if (nx + 1 < x && nx - 1 >= 0 && ny - 1 >= 0)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny][nx - 1] + arr[ny - 1][nx + 1] + arr[ny - 1][nx]);
    }
    if (nx + 1 < x && nx - 1 >= 0 && ny - 1 >= 0)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny][nx + 1] + arr[ny - 1][nx - 1] + arr[ny - 1][nx]);
    }
    //cout<<"form4's return is "<<tmp<<endl;
    return tmp;
}

int form5(int nx, int ny)
{
    int tmp = 0;
    if (nx + 2 < x && ny - 1 >= 0)
    {
        tmp = arr[ny][nx] + arr[ny][nx + 1] + arr[ny][nx + 2] + arr[ny - 1][nx + 1];
    }
    if (nx + 2 < x && ny + 1 < y)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny][nx + 1] + arr[ny][nx + 2] + arr[ny + 1][nx + 1]);
    }
    if (nx - 1 >= 0 && ny + 2 < y)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny + 1][nx] + arr[ny + 2][nx] + arr[ny + 1][nx - 1]);
    }
    if (nx + 1 < x && ny + 2 < y)
    {
        tmp = max(tmp, arr[ny][nx] + arr[ny + 1][nx] + arr[ny + 2][nx] + arr[ny + 1][nx + 1]);
    }
    //cout<<"form5's return is "<<tmp<<endl;
    return tmp;
}

int main()
{
    cin >> y >> x;
    ans = 0;
    for (int i = 0; i < y; i++)
    {
        for (int j = 0; j < x; j++)
        {
            cin >> arr[i][j];
        }
    }
    for (int i = 0; i < y; i++)
    {
        for (int j = 0; j < x; j++)
        {
            ans = max(ans, max(form1(j, i), max(form2(j, i), max(form3(j, i), max(form4(j, i), form5(j, i))))));
        }
    }
    cout << ans << '\n';
    return 0;
}

6064 카잉 달력

이 문제도 비슷하게 브루트포스 알고리즘으로 푸는 문제이다. 다만 자료형의 크기가 비교적 크고 (최대 40000) 모든 탐색을 수행하기에는 시간복잡도에 문제가 있다. 따라서 필요한 부분만 확인하는 연산이 필요하다.

어제 푼 날짜계산 문제와 비슷한 문제이지만 비교할 날짜가 두개밖에 없다. 따라서 한 값을 이미 정답으로 고정해놓고 다른 값이 정답일 때까지 반복연산하면 어느순간 정답을 구할 수 있게 된다.

단, 최대공배수를 초과하여 연산을 했을 때도 값을 찾지 못했다면 그건 없다고 봐야한다.

m=5 n=4 / x=2 y=4 일 때

cnt	x	y
1	1	1
2	2	2
3	3	3
4	4	4
5	5	1
6	1	2
7	2	3
8	3	4
9	4	1
10	5	2
11	1	3
12	2	4
13	3	1

이 경우 cnt가 y값을 충족할 때만 굵은 글씨로 표시했다. 이러한 반복은 아래와 같다.

for (int i = y; i < (m * n); i += n)

이 반복문 안에서 x값이 충족하는지 알기 위해서는 조건문을 사용하면 된다.
if (i % m == x)

여기서 주의할 점은 x와 y를 1씩 빼주고 연산을 수행해야 한다는 점이다.

위의 예를 들어보면 4를 4로 나눈 나머지는 0이다. 당연한 말이다. 그러나 이 때 우리가 원하는 값은 4이다. 이러한 예외는 n과 m의 배수마다 처리해줘야 한다.

이러한 예외처리를 원하지 않는다면 x와 y의 값을 1씩 빼준 뒤 cnt를 1 더해주면 된다.

간접적인 연산을 통해 원하는 값을 구하는 식이다.

x와 y의 값을 1씩 더한 뒤 cnt를 1 빼주면 카잉달력의 수 법칙이 무너질 수 있다. 그러나 이보다 작은 수를 처리하는 것은 문제가 없다.

정리하면 나머지 연산의 예외로 인해 나누는 수보다 1 작은 수까지만 계산하고 그보다 1 큰 값을 출력하는 것이 핵심이다.

#include <iostream>
using namespace std;

int t, m, n, x, y;
bool ok;

int main()
{
    cin >> t;
    while (t--)
    {
        cin >> m >> n >> x >> y;
        x -= 1;
        y -= 1;
        ok = false;
        for (int i = y; i < (m * n); i += n)
        {
            if (i % m == x)
            {
                cout << i + 1 << '\n';
                ok = true;
                break;
            }
        }
        if (ok == false)
            cout << -1 << '\n';
    }
}

1748 수 이어 쓰기 1

예제로 120이라고 생각해보면

• 1 - 9 -> (9 - 1 + 1) * 1
• 10 - 99 -> (99 - 10 + 1) * 2
• 100 - 120 -> (120 - 100 + 1) *3

이걸 변수로 바꿔보면
(자릿수 끝지점 - 자릿수 시작지점 + 1) * 현재 자릿수

#include <iostream>
using namespace std;

long long n, ans;

int main()
{
    cin >> n;
    for (int start = 1, len = 1; start <= n; start *= 10, len++)
    {
        int end = start * 10 - 1;
        if (end > n)
            end = n;
        ans += (end - start + 1) * len;
    }
    cout << ans << '\n';
}

강의 참고해서 풀었는데 for문 이렇게 쓸 수 있는줄 몰랐다...ㅎ