BrianaAI

#문제.

https://softeer.ai/practice/7628

#정답.

import sys

'''
6
2 4 6 9 12 18
'''
chance = int(sys.stdin.readline())
num_list = list(map(int, sys.stdin.readline().split()))
max_num = max(num_list)
if max_num > 100:
    max_num = 100
top_max_value = 0
for i in range(2, 101):
    cnt = 0
    for n in num_list:
        if n % i == 0:
            cnt += 1
    if top_max_value < cnt:
        top_max_value = cnt
print(top_max_value)

안녕하세요.

브리아나입니다.

반례때문에 한참을 풀었네요..휴..(질문게시판 보고 알았습니다)

문제.

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

풀이.

N, M = map(int, input().split())
arr = []
virus = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(N):
        if arr[i][j] == 2: # 바이러스
            virus.append((i, j))
            arr[i][j] = 0 # 미리 바이러스 가능공간 0으로 없애버리기
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def solve(tlst):
    # make a wall
    w = [[0] * N for _ in range(N)]

    # [1] virus 넣어
    q = []
    for tx, ty in tlst:
        w[tx][ty] = 1
        q.append((tx, ty))

    m = 0
    while q:
        cx, cy = q.pop(0)
        for i in range(4):
            nx, ny = cx+dx[i], cy+dy[i]
            if 0<=nx<N and 0<=ny<N and w[nx][ny] == 0 and arr[nx][ny] == 0:
                w[nx][ny] = w[cx][cy]+1
                q.append((nx, ny))
                m = max(m, w[nx][ny])

    for i in range(N):
        for j in range(N):
            if w[i][j] == 0 and arr[i][j] == 0: # 그냥 길인데, 방문안한곳이 있다면
                return float("inf")
    # print("m: ", m-1, tlst)
    if m>0:
        return m-1
    return m


ans = float("inf")

def bfs(n, lst):
    global ans
    if len(lst) == M:
        ans = min(ans, solve(lst))
        return

    for i in range(n, len(virus)):
        if v[i] == 0:
            v[i] = 1
            bfs(i+1, lst+[virus[i]])
            v[i] = 0
    return

v = [0]*(len(virus))
bfs(0, [])

if ans == float("inf"):
    ans = -1
print(ans)

반례. 놓자마자 퍼짐. 그래서 저의 경우 0이 아닌 -1이 출력 되어서

5 2
1 1 1 1 1
1 1 2 1 1
1 1 2 1 1
1 1 1 1 1
1 1 1 1 1

if m>0:

return m-1

return m

이 문장을 넣어줬어요...휴...

안녕하세요.

브리아나입니다.

오늘은 백트래킹 말고,

시간 더 단축시킬 수 있는 경우를 풀어보겠습니다.

그래도 3개라는 숫자가 주어지니까 가능한 버전입니다.

문제.

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

풀이.

N, M = map(int, input().split())
arr = []
path = []
virus = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(M):
        if arr[i][j] == 0:
            path.append((i, j))
        elif arr[i][j] == 2:
            virus.append((i, j))

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def bfs(tlst):
    # [1] make wall 3 times
    for tx, ty in tlst:
        arr[tx][ty] = 1

    # [2] initialize virus info
    q = []
    w = [[0]*M for _ in range(N)]
    for vx, vy in virus:
        w[vx][vy] = 1
        q.append((vx, vy))
    chance = cnt-3

    while q:
        cx, cy = q.pop(0)
        for i in range(4):
            nx, ny = cx+dx[i], cy+dy[i]
            if 0<=nx<N and 0<=ny<M and w[nx][ny] == 0 and arr[nx][ny] == 0:
                w[nx][ny] = 1
                q.append((nx, ny))
                chance-=1

    # reset
    for tx, ty in tlst:
        arr[tx][ty] = 0

    return chance


cnt = len(path)
ans = 0

for i in range(cnt-2):
    for j in range(i+1, cnt-1):
        for k in range(j+1, cnt):
            ans = max(ans, bfs([path[i], path[j], path[k]]))
print(ans)

참고하세요 ~~

안녕하세요.

백트래킹을 공부하고 싶은 사람 있으면

N과 M 시리즈부터 공부를 해야해요.

https://www.acmicpc.net/workbook/view/2052

여기 들어가면 시리즈가 있습니다.

1번부터 12번까지의 저의 풀이 남기겠습니다. :) 화잇팅

#1.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]
def DF(lst):
    if len(lst)==M:
        print(" ".join(map(str, lst)))
        return
    for i in range(1, N+1):
        DF(lst+[tmp[i]])
DF([])

#2.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]
v = [0]*(N+1)

def DF(lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return
    for i in range(1, N+1):
        if v[i] == 0:
            v[i] = 1
            DF(lst+[tmp[i]])
            v[i] = 0
DF([])

#3.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]
v = [0]*(N+1)

def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for i in range(s, N+1):
        if v[i] == 0:
            v[i] = 1
            DF(i, lst+[tmp[i]])
            v[i] = 0
DF(1, [])

#4.

N, M = map(int, input().split())
tmp = [i for i in range(N+1)]

def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for i in range(s, N+1):
        DF(i, lst+[tmp[i]])

DF(1, [])

#5.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
v = [0]*(N+1)

def DF(lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for idx, i in enumerate(arr):
        if v[idx] == 0:
            v[idx] = 1
            DF(lst+[arr[idx]])
            v[idx] = 0
DF([])

#6.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
v = [0]*(N)
def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        if v[i] == 0:
            v[i] = 1
            DF(i, lst+[arr[i]])
            v[i] = 0
DF(0, [])

#7.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
def DF(lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return

    for i in range(len(arr)):
        DF(lst+[arr[i]])
DF([])

#8.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
def DF(s, lst):
    if len(lst) == M:
        print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        DF(i, lst+[arr[i]])
DF(0, [])

# 9.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ll = []
v = [0]*N
def DF(lst):
    if len(lst) == M:
        if lst not in ll:
            print(" ".join(map(str, lst)))
            ll.append(lst)
        return
    for i in range(len(arr)):
        if v[i] == 0:
            v[i] = 1
            DF(lst+[arr[i]])
            v[i] = 0
DF([])

#10.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
v = [0]*N
ll = []

def DF(s, lst):
    if len(lst) == M:
        if lst not in ll:
            ll.append(lst)
            print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        if v[i] == 0:
            v[i] = 1
            DF(i, lst+[arr[i]])
            v[i] = 0
DF(0, [])

# 11.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ll = []

def DF(lst):
    if len(lst) == M:
        if lst not in ll:
            print(" ".join(map(str, lst)))
            ll.append(lst)
        return
    for i in range(len(arr)):
        DF(lst+[arr[i]])
DF([])

#12.

N, M = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
ll = []
def DF(s, lst):
    if len(lst) == M:
        if lst not in ll:
            ll.append(lst)
            print(" ".join(map(str, lst)))
        return
    for i in range(s, len(arr)):
        DF(i, lst+[arr[i]])
DF(0, [])