[boj][c++] 3085 사탕게임, 1476 날짜계산

3085 사탕게임

브루트포스 알고리즘 강의 듣기 전에 푼 문제다. 울며 겨자먹기로 해결했다. 처음에는 각 탐색마다 행/열에 있는 색상의 수를 모두 저장하는 식으로 로직을 짰는데 코드가 너무 복잡해졌다.

어차피 출력은 그 중 가장 긴 연속된 색상의 수만 나오므로 그냥 max_e 라는 전역변수를 사용해서 값을 저장했다.

문제를 풀기 어려웠던 이유는 algorithm 헤더에 swap 내장함수가 있는지 몰랐기 때문...ㅋㅋ; 변명이지만 길어지는 코드를 보며 터졌던 멘탈을 내장함수로 다잡을 수 있었다.

로직은 브루트포스 알고리즘이 대부분 그렇듯 무지성 완전탐색이다.

• 메인에서 각 원소의 오른쪽/아래 원소를 각각 한번씩 뒤집는다.
• 탐색을 통해 그 때의 모든 행/열 중 연속된 색이 가장 길게 이어지는 값을 저장한다.
• 1번과 2번을 n * n 번만큼 반복한다.

주의할 점은 당연히 배열의 원소를 반복문으로 비교하기 때문에 배열의 인덱스를 벗어난 값과 비교 연산하지 않게 코드를 짜는 것이다. 단순한 문제지만 구현이 조금 빠ㅓㄱ셌다 . . .

나는 늘 그렇듯이 x좌표와 y좌표의 이름이 바뀌는 순간부터 헷갈리기 시작해서 몇번을 재도전했다. 잘못된 코드라는게 느껴지는데 문제에서 제시된 입력에서는 출력이 제대로 돼서 당황스러웠다. ㅎ

낯선 구현에게 익숙해지는 연습을 해야겠다. 정형화 된 문제만 풀다보니 딱 그 유형의 문제밖에 못푸는 상태가 돼버렸다.

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

int n, max_e, ans;
char arr[51][51];

void search()
{
    for (int i = 0; i < n; i++)
    {
        char c = arr[i][0];
        int cnt = 1;
        for (int j = 1; j < n; j++)
        {
            if (arr[i][j] == c)
                cnt++;
            else
                cnt = 1;
            c = arr[i][j];
            if (max_e < cnt)
                max_e = cnt;
        }
    }
    for (int i = 0; i < n; i++)
    {
        char c = arr[0][i];
        int cnt = 1;
        for (int j = 1; j < n; j++)
        {
            if (arr[j][i] == c)
                cnt++;
            else
                cnt = 1;
            c = arr[j][i];
            if (max_e < cnt)
                max_e = cnt;
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - 1; j++)
        {
            swap(arr[i][j], arr[i][j + 1]);
            search();
            swap(arr[i][j], arr[i][j + 1]);
            if (ans < max_e)
                ans = max_e;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - 1; j++)
        {
            swap(arr[j][i], arr[j + 1][i]);
            search();
            swap(arr[j][i], arr[j + 1][i]);
            if (ans < max_e)
                ans = max_e;
        }
    }
    cout << ans << '\n';
}

1476 사탕게임

15 * 28 * 19 = 7980 으로 연산 횟수에 문제가 없음. 각 기준점이 지날때마다 변수를 1로 초기화하고 ans 는 계속 증가함.

조건이 충족됐을 때 출력하고 중단함.

#include <iostream>
using namespace std;

int e, s, m, e1, s1, m1, ans;

int main()
{
    cin >> e >> s >> m;
    ans = 0;
    while (1)
    {
        ans++;
        if (e1 < 15)
            e1++;
        else
            e1 = 1;
        if (s1 < 28)
            s1++;
        else
            s1 = 1;
        if (m1 < 19)
            m1++;
        else
            m1 = 1;
        if (e1 == e && s1 == s && m1 == m)
        {
            cout << ans << '\n';
            return 0;
        }
    }
}

아래는 조금 더 똑똑한 코드

#include <iostream>
using namespace std;

int e, s, m, ans;

int main()
{
    cin >> e >> s >> m;
    e -= 1;
    s -= 1;
    m -= 1;
    for(int i = 0;;i++)
    {
        if(i % 15 == e && i % 28 == s && i % 19 == m)
        {
            cout<<i<<'\n';
            return (0);
        }     
    }
}

코드

앞으로는 shift + option + f 로 코드 정렬하고 업로드하자. 클린코드...!