[Baekjoon - 2115] 갤러리

난이도: Gold V

 

태그

• Greedy

 

풀이

1. 방향이 다른 두 그림이 겹칠 수 있을까?

만약 겹친다면, 아래와 같은 느낌이 될 겁니다.

90도로 만나는 경우 / 180도로 만나는 경우

 

하지만 위 경우를 만들어낼 수 있는 벽의 배치가 존재하지 않기 때문에, 걱정하지 않아도 된다는 결론이 나옵니다.

 

2. 방향을 고정했을 때, 걸 수 있는 그림의 개수는?

하나의 벽의 길이가 \( X \)라면, 그 벽에 \( \left\lceil \frac{X}{2} \right\rceil \)개의 그림을 걸 수 있습니다.

길이가 7인 벽에 3개의 그림을 거는 방법의 예시

 

위 식을 특정 방향을 보는 모든 벽에 대해 다 구해주면 되겠죠.

 

3. 구현 디테일

저의 경우는 벽의 길이를 계산하는 대신, 그림을 걸 수 있는 경우가 나오면 바로 그림을 건다고 한 뒤

그림이 겹치게 되는 경우를 건너뛰게 했습니다.

 

4. 코드

char mp[1020][1020];
 
void Main(){
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){ cin >> mp[i][j]; }
    }
    int ans = 0;
    for (int i = 1; i < n; i++){
        for (int j = 1; j < m; j++){
            if (mp[i][j]==mp[i][j+1] && mp[i+1][j]==mp[i+1][j+1] && mp[i][j]!=mp[i+1][j+1]){ ans += 1; j += 1; }
        }
    }
    for (int j = 1; j < m; j++){
        for (int i = 1; i < n; i++){
            if (mp[i][j]==mp[i+1][j] && mp[i][j+1]==mp[i+1][j+1] && mp[i][j]!=mp[i+1][j+1]){ ans += 1; i += 1; }
        }
    }
    cout << ans;
}