2*n 배열이 주어진다.
첫번째 행은 숫자들이 쓰여있는데 그 블록 주위에 지뢰가 몇개 있는지를 나타낸다.
두번째 행은 지뢰가 숨겨져 있는 행인데, *, #으로만 주어진다. *은 지뢰이다.
예를 들어
11122
####*로 주어진다면
첫번째 #은 바로 위에 1이 쓰여있고, 우측 대각선 상단에 1이 쓰여있으므로 지뢰가 있을 수 있다.
11122
*###*
그리고 4번째 #에는 왼쪽 대각선 상단에 1, 바로 위 2, 우측 대각선 상단에 2가 쓰여있는 것으로 보아 지뢰가 있을 수 있다
11122
*##**
이때 *을 포함해서 숨겨진 지뢰의 최대 개수를 구한다.
----------------------------------------------------------------------------------------------------------------------------------------------------------------
0번의 숫자를 확인해보고, 0번의 숫자가 영향을 미칠 수 있는 곳에 있는 지뢰의 개수를 체크해본다
그리고 그에 맞게 지뢰를 설치한다
1번부터 n-2번까지 숫자를 확인해보고 마찬가지로 영향을 미칠 수 있는 곳에 있는 지뢰의 개수를 구한다.
그리고 그에 맞게 지뢰를 설치한다
보면 알겠지만 i번 숫자를 확인할 때는 0~i번까지는 지뢰가 확정되어 있다.
즉, i+1번의 지뢰만 결정하게 된다.
즉, i번의 숫자가 x라고 적혀있고, i번에 대하여 i-1번, i번, i+1번에 지뢰가 있는지 체크하게 될텐데,
현재 지뢰가 있는 개수가 count개라고 한다면, x-count개의 지뢰를 새로 설치해야한다.
그러면 i-1번, i번, i+1번 중 x-count개의 지뢰는 어디에 설치해야하는가?
이미 i-1,i번은 설치가 확정되어 있으므로, 반드시 i+1번에만 설치해야한다.
즉, x-count는 0 아니면 1이다.
이후 지뢰를 설치하면 다시 처음부터 순회해서 지뢰의 개수를 구하면 그것이 정답
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
n = int(stdin.readline())
s1 = stdin.readline().rstrip()
s2 = list(stdin.readline().rstrip())
x = int(s1[0])
count = 0
for i in range(x):
if s2[i] == '*':
count += 1
for i in range(x-count):
s2[i] = '*'
for i in range(1,n-1):
x = int(s1[i])
count = 0
for j in range(i-1,i+1):
if s2[j] == '*':
count += 1
r = x - count
if r == 1:
s2[i+1] = '*'
count = 0
for i in range(n):
if s2[i] == '*':
count += 1
print(count)
근데 조금 더 아름다운? 풀이가 있는데,
지뢰의 최대 개수가 m개라고 하자.
지뢰의 위치당 숫자의 총 합에 기여할 수 있는 양이 정해져있다.
양 끝쪽은 2만큼 기여할 수 있고, 1~n-1번은 3만큼 기여할 수 있다.
지뢰의 총 개수가 m개라고 할때, 양 끝 쪽에 있는 지뢰의 개수가 i개라고 한다면,
2i + 3(m-i) = (1행의 숫자 합)
1행의 숫자 합을 s라 하고 이것을 구한 다음 i = 0,1,2부터 해봐서 가능한 m의 최댓값을 찾으면 된다
이때 s - 2i가 3으로 나누어 떨어져야겠지
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
n = int(stdin.readline())
s1 = list(map(int,input()))
s2 = list(stdin.readline().rstrip())
s = sum(s1)
m = 0
for i in range(3):
#2*i + 3*(m-i) = s
if (s-(2*i)) % 3 == 0:
x = (s - (2*i))//3
if m < x+i:
m = x+i
print(m)
----------------------------------------------------------------------------------------------------------------------------------------------------------
이번엔 N*N 배열이 주어지는데, 테두리에 숫자들이 쓰여있고, 그 안쪽은 모두 #으로 닫혀있다.
이때, #에 존재할 수 있는 지뢰의 최대 개수를 찾는다.
숫자는 그 칸과 8방향으로 인접해 있는 곳에 있는 지뢰의 개수를 알려준다.
---------------------------------------------------------------------------------------------------------------------------------------------------------------
왼쪽 상단 대각선부터 시작해서, 시뮬레이션 하면서 지뢰를 설치할 수 있으면 일단 설치하면 된다.
각 지점에서 지뢰를 설치하는 경우, 8방향을 검사해서 숫자가 적힌 곳이면 1씩 빼줘야한다.
지뢰를 설치할 수 있는 곳은 어떤 곳인가?
8방향을 모두 검사해서, 숫자가 쓰여있는 곳이라면, 그 숫자들이 모두 1이상이어야 한다.
빨간색은 설치할 수 있는 곳인데
1이상인 숫자가 하나라도 없다면, 그곳에는 지뢰를 설치할 수 없다.
아래 파란색 동그라미 부분은 설치할 수 없는 곳이다
이렇게 하면, 숫자 테두리와 인접한 안쪽 테두리 부분은 지뢰를 모두 설치하게 된다.
이제 그 안쪽 부분은 아무런 제약조건이 없으므로, 지뢰의 최대 개수를 구해야하기 때문에 무조건 설치하면 된다.
그 안쪽 부분은 몇개인가?
(n-4) * (n-4)개
그러면 예외가 생기게 된다
n = 1인 경우 1*1에는 숫자만 쓰여있으므로 지뢰가 없다 0개
n = 2인 경우도 마찬가지
n = 3인 경우는 안쪽이 1개만 있는데 모두 1로 쓰여있거나, 모두 0으로 쓰여있거나 둘중 하나여야 한다.
따라서 왼쪽 대각선 (0,0) 부분이 1이면 지뢰가 1개, 아니라면 지뢰가 0개
n=4부터는 위 방식대로 시뮬레이션 하면 된다
from sys import stdin
n = int(stdin.readline())
maps = [list(stdin.readline().rstrip()) for _ in range(n)]
if n <= 2:
print(0)
else:
if n == 3:
if maps[0][0] == '1':
print(1)
else:
print(0)
else:
maps[0] = list(map(int,maps[0]))
maps[-1] = list(map(int,maps[-1]))
for i in range(1,n-1):
maps[i][0] = int(maps[i][0])
maps[i][-1] = int(maps[i][-1])
x,y = 1,1
delta1 = [[1,0],[0,1],[-1,0],[0,-1]]
delta2 = [[0,1],[1,0],[0,-1],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]]
i = 0
m = 0
while 1:
if maps[y][x] == '#':
find = True
for a,b in delta2:
dx = x + a
dy = y + b
if maps[dy][dx] != '#' and maps[dy][dx] != '*':
if maps[dy][dx] == 0:
find = False
break
if find:
for a,b in delta2:
dx = x + a
dy = y + b
if maps[dy][dx] != '#' and maps[dy][dx] != '*':
if maps[dy][dx] >= 1:
maps[dy][dx] -= 1
maps[y][x] ='*'
m += 1
a,b = delta1[i]
x = x + a
y = y + b
if x == n-1 or y == n-1 or x == 0 or y == 0:
x = x - a
y = y - b
i += 1
a,b = delta1[i]
x = x + a
y = y + b
if x == 1 and y == 1:
break
print(m + (n-4)*(n-4))
마찬가지로 위에서 2*n배열 풀때처럼 애드혹적인 방식으로도 해결 가능하다.
안쪽 테두리에서 모서리쪽에는 지뢰가 있는지 없는지 확신할 수 있다
(0,0), (0,-1), (-1,0), (-1,-1) 부분이 1인지 아닌지를 체크하면 된다.
이 부분은 오직 모서리쪽만 관여할 수 있으니까
이 4방향 꼭짓점 이외에는 나머지 부분은 모두 합에 3을 기여하게 된다
그래서 먼저 테두리 숫자 합을 s라 하자.
이제 꼭짓점 부분을 확인해서 확실하게 지뢰를 알 수 있는 곳을 체크한다.
(0,0)이 1인지, (0,-1)이 1인지, (-1,0)이 1인지, (-1,-1)이 1인지...
이제 지뢰가 있는 곳이라면 카운팅 해주고 합에 5를 빼주면 된다.
왜냐하면 꼭짓점 부분은 5방향에 기여하게 되니까
이렇게 체크하고 나서 변경된 합이 s라 한다면,
그리고 나머지 부분은 모두 합에 3을 기여하므로, 3m = s니까, m을 구할 수 있다.
이 m에다가 꼭짓점 부분 지뢰 개수 합에 나머지 안쪽 부분 (n-4)*(n-4)개를 더하면 그것이 정답
n = 1,2,3인 경우는 위에서 한 것처럼 예외처리
from sys import stdin
n = int(stdin.readline())
maps = [list(stdin.readline().rstrip()) for _ in range(n)]
if n <= 2:
print(0)
else:
s = 0
s += sum(map(int,maps[0]))
s += sum(map(int,maps[-1]))
for i in range(1,n-1):
s += (int(maps[i][0]) + int(maps[i][-1]))
if n == 3:
if s == 8:
print(1)
else:
print(0)
else:
m = 0
if maps[0][0] == '1':
m += 1
s -= 5
if maps[0][-1] == '1':
m += 1
s -= 5
if maps[-1][0] == '1':
m += 1
s -= 5
if maps[-1][-1] == '1':
m += 1
s -= 5
print(m + s//3 + (n-4)*(n-4))'알고리즘 > 애드 혹 알고리즘' 카테고리의 다른 글
| 원 위에서 정삼각형을 이루게 하는 점을 고르는 방법 (0) | 2025.06.15 |
|---|---|
| 0이나 1을 뒤집어서 1이 연속인 구간이 최대 1개로 만들기 (0) | 2025.06.05 |
| 인접한 두 수를 분해하여 적절하게 바꿔서 정렬하는 방법 (0) | 2025.04.10 |
| 구간 내 가장 큰 해밍거리를 가지는 두 정수를 구하는 방법 (0) | 2025.04.08 |
| 야바위에서 바로 왼쪽이나 오른쪽으로 한번만 이동시킬 수 있을때 가능한 위치 구하기 (0) | 2025.03.26 |