📚 9082 - 지뢰찾기

지뢰찾기

이해

지뢰찾기 게임

12110
##*##

일 때,

1 : 0번과 1번 중 지뢰가 1개가 존재한다.
2 : 0, 1, 2번 중 지뢰가 2개가 존재한다.
1 : 1, 2, 3번 중 지뢰가 1개가 존재한다.
1 : 2, 3, 4번 중 지뢰가 1개가 존재한다.
0 : 3, 4, 5번 중 * 지뢰가 0개가 존재한다.

➡ 첫 번째부터 검사하면서 지뢰의 개수를 줄여주면 된다.

✔ 규칙
i번째, i+1번째, i+2번째가 있을 때
지뢰가 최대 : 2 3 2개가 가능하다.

• i번째 검사 : i번째와 i+1번째 검사로 총 2번 검사 (최대 지뢰 2개가 존재할 수 있다.)
• i+1번째 검사 : i번째, i+1번째, i+2번째 검사로 총 3번 검사 (최대 지뢰 3개가 존재할 수 있다.)
• i+2번째 검사 : i+1번째, i+2번째 검사로 총 2번 검사 (최대 지뢰 2개가 존재할 수 있다.)

➡ 인덱스 0번째부터 검사하며 인덱스 검사 범위내에 한 블록에 쓰여진 숫자 0이 존재하지 않는다면 해당 구역에 지뢰 개수를 1씩 줄인다.
➡ 1 2 1 이고, 인덱스 1번째 (2)를 검사하고 있을 때 0, 1, 2번째에 0이 존재하지 않으므로 지뢰 개수를 1씩 줄여준다.

💡 참고

• 지뢰 갯수 찾기 공식이 존재한다.
• 지뢰 경우의 수 총합에서 0번째, n-1번째가 각각 0이 아니라면 1씩 더 한후, 3으로 나눈 몫이 지뢰 개수를 구할 수 있다.
  • ex)
  • 1 2 3 3 2 1 인경우
  • 12 + (처음 1 + 끝 1) = 14
  • 14 // 3 = 4

소스

import sys

read = sys.stdin.readline

t = int(read())

for i in range(t):
    n = int(read())

    block = list(map(int, read().rstrip()))
    block2 = list(read().rstrip())
    answer = 0

    for j in range(n):
        if j == 0 and block[j] != 0 and block[j + 1] != 0:
            block[j] -= 1
            block[j + 1] -= 1
            answer += 1
        elif j == n - 1 and block[j] != 0 and block[j - 1] != 0:
            block[j] -= 1
            block[j - 1] -= 1
            answer += 1
        elif 1 <= j <= n - 2 and block[j - 1] != 0 and block[j] != 0 and block[j + 1] != 0:
            block[j] -= 1
            block[j - 1] -= 1
            block[j + 1] -= 1
            answer += 1
    print(answer)