[백준/Baekjoon] 3085 사탕 게임 C++ :: Brute force

 

https://www.acmicpc.net/problem/3085

3085번: 사탕 게임

---

1. Logic

1. 인접한 두 칸에 있는 사탕을 서로 바꿔야하기 때문에 swap함수를 사용해서 값을 변경해 준다. 

2. 같은 색의 사탕을 먹어야 하기 때문에 현재칸과 그 다음칸을 비교하면서 진행하며 cnt를 올려준다.

3. 최댓값을 갱신해준다. 

 

 

---

728x90

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<string> vec;

int n;

int calc() {
    // 가로
    int ans = -92735;
    
    for(int i = 0; i < n; i++) {
        int cnt = 1;
        for(int j = 0; j < n - 1; j++) {
            if(vec[i][j] == vec[i][j + 1]) {
                cnt++;
            }
            else {
                ans = max(ans, cnt);
                cnt = 1;
            }
        }
        ans = max(ans, cnt);
    }

    //세로
    for(int i = 0; i < n; i++) {
        int cnt = 1;
        for(int j = 0; j < n - 1; j++) {
            if(vec[j][i] == vec[j + 1][i]) {
                cnt++;
            }
            else {
                ans = max(ans, cnt);
                cnt = 1;
            }    
        }
        ans = max(ans, cnt);
    }

    
    return ans;
}

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

    int ans = -98764123;

    cin >> n;

    for(int i = 0; i < n; i++) {
        string str;
        cin >> str;

        vec.push_back(str);
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n - 1; j++) {
            swap(vec[i][j], vec[i][j + 1]);
            ans = max(ans, calc());
            swap(vec[i][j], vec[i][j + 1]);
            
            swap(vec[j][i], vec[j + 1][i]);
            ans = max(ans, calc());
            swap(vec[j][i], vec[j + 1][i]);
        }
    }

    cout << ans;
}

 

 

---

 

 

3. Feedback

1. 문제를 잘 읽자. - 같은색으로 이루어진 사탕을 먹어야하는 데 문제를 꼼꼼히 안읽어서 처음에 전체 사탕 갯수를 구했다. 나중에 코딩테스트를 볼때 이러한 과정은 시간낭비로 이어지기때문에 문제를 더욱 꼼꼼히 파악하도록 노력해야겠다.

 

2. STL에서 swap 함수를 잊어버려 직접 상하/좌우 value를 swap하는 함수를 구현했다. - STL 숙지 필요