백준 9082번: 지뢰찾기 (JAVA)

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

9082번: 지뢰찾기

문제

지뢰찾기 게임은 2×N 배열에 숨겨져 있는 지뢰를 찾는 게임이다. 지뢰 주위에 쓰여 있는 숫자들로 지뢰를 찾을 수 있는데, 한 블록에 쓰여진 숫자는 그 블록 주위에 지뢰가 몇 개 있는지를 나타낸다. 지뢰가 확실히 있는 위치를 *, 숨겨진 블록을 #으로 표시한다. 첫째 줄에는 숫자만 나타나고 둘째 줄에는 *와 #만 나타나는데, 지뢰는 둘째 줄에만 있다.

12110
##*##

위의 그림 2×5 배열에는 지뢰가 2개가 있다는 것을 알 수 있다. 숨겨진 블록 중 첫 번째 블록에 지뢰가 숨겨져 있고, 나머지 하나는 두 번째 줄의 가운데에 있다.

2×N 배열이 주어지면 주어진 배열에 있는 모든 지뢰의 개수(*까지 포함)를 찾는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 첫 줄에 배열의 크기 N(1 ≤ N ≤ 100)이 주어지고, 그 다음 두 줄에 걸쳐서 배열이 주어진다. 첫 줄에는 항상 숫자만이 나타나며 이 숫자들 사이에 공백은 없으며, 둘째 줄에 주어지는 입력들 사이에도 공백은 없다. 그리고 이 숫자들은 올바른 값만이 입력으로 들어온다(지뢰의 위치에 대해 불가능한 값은 입력으로 주지 않는다).

출력

각 테스트 케이스에 대해서 주어진 배열에 있는 모든 지뢰의 수를 한 줄에 하나씩 출력한다. 지뢰의 수가 여럿이 될 수 있으면 가능한 지뢰의 수 중 최댓값을 출력한다.

 

---

 

풀이

'가능한 지뢰의 수 중 최댓값'에서 뭔가 그리디적인 접근법일거라 생각했다. 근데 생각해보면, '지뢰의 위치에 대해 불가능한 값은 주어지지 않는다'고 했기에, 지뢰 배치 신경 안 쓰고 그냥 '주변 지뢰의 수' 를 다 더한 값(total이라 부르자.)만 있으면 지뢰가 몇 개 있을지 결정된다. 왜냐하면, 2*N 판에서 지뢰는 맨 앞, 맨 뒤는 2칸에 영향을 미치고, 나머지는 3칸에 영향을 미치기에,

1. total이 3의 배수: 맨 앞 or 맨 뒤에 지뢰가 있을 수가 없다. 따라서 total/3개.

2. total % 3 == 1: 안 되는 경우 생각할 필요 없이 앞뒤 모두에 지뢰를 배치하고, 중간에 적당히 (total-4)/3개의 지뢰를 배치하면 된다.

3. total % 3 == 2: 앞이든 뒤든 하나의 지뢰를 배치하고, (total-2)/3개의 지뢰는 중간에 적당히 배치할 수 있다.

 

 

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int total = 0;
            int N = Integer.parseInt(br.readLine());
            String str = br.readLine();
            for (int i = 0; i < str.length(); i++) {
                total += (str.charAt(i) - '0');
            }
            br.readLine();
            System.out.println((total+2)/3);
        }
    }
}