[boj] (s3) 3085 사탕 게임

2851 단어 bojboj

문제

링크

풀이

사탕위치를 인접한 사탕과 모두 바꿔봐야 하므로 완전 탐색문제이다.
완전탐색이기 때문에 풀이자체는 단순하고, 특별한건..

  1. c++에서는 하나의 문자열을 하나의 문자 배열처럼 접근할 수 있다
  2. 오른쪽, 아래쪽 사탕과 위치를 교환할때 정해진 크기 이상을 참조하는 경우를 주의해야한다
  3. 인접한 사탕이 같은 사탕인 경우를 세는 방법은 아래 코드의 count() 처럼 한칸씩 이동하면서 바로 이전 사탕과 같을때 ++ 해주고 아니면 초기화 해주는 방법이 편하다

1, 3번이 새로 알게된 사실이다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

int N, sum, ans = 0;

void count(string *candy)
{
    for(int i=0;i<N;i++){
        sum=1;
        for(int j=1;j<N;j++){
            if (candy[i][j] == candy[i][j - 1])
            {
                sum += 1;
                if (sum > ans)
                    ans = sum;
            }
            else
                sum = 1;
        }
    }

    for(int j=0;j<N;j++){
        sum = 1;
        for(int i=1;i<N;i++){
            if (candy[i][j] == candy[i - 1][j])
            {
                sum += 1;
                if (sum > ans)
                    ans = sum;
            }
            else
                sum = 1;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    string candy[N];

    for (int i = 0; i < N; i++)
    {
        cin >> candy[i];
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (j + 1 < N)
            {
                // 오른쪽과 교환
                swap(candy[i][j], candy[i][j + 1]);

                count(candy);

                // 원위치
                swap(candy[i][j], candy[i][j + 1]);
            }

            if (i + 1 < N)
            {
                // 아래쪽과 교환
                swap(candy[i][j], candy[i + 1][j]);

                count(candy);

                // 원위치
                swap(candy[i][j], candy[i + 1][j]);
            }
        }
    }

    cout << ans;
}

좋은 웹페이지 즐겨찾기