★BF Advanced I - 3 Solved★

★ 14500 테트로미노 ★

 

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
tetris=[]
for _ in range(N):
    tetris.append(list(map(int,input().split())))
ans=0
for i in range(N):
    for j in range(M):
        #1x4
        if j<=(M-4):
            cur=tetris[i][j]+tetris[i][j+1]+tetris[i][j+2]+tetris[i][j+3]
            ans=max(cur,ans)
        #4x1
        if i<=(N-4):
            cur=tetris[i][j]+tetris[i+1][j]+tetris[i+2][j]+tetris[i+3][j]
            ans=max(cur,ans)
        #2x2
        if i<=(N-2) and j<=(M-2):
            cur=tetris[i][j]+tetris[i+1][j]+tetris[i][j+1]+tetris[i+1][j+1]
            ans=max(cur,ans)
        #2x3
        if i<=(N-2) and j<=(M-3):
            a,b,c,d,e,f=tetris[i][j],tetris[i][j+1],tetris[i][j+2],tetris[i+1][j],tetris[i+1][j+1],tetris[i+1][j+2]
            ans=max(a+b+c+e,ans)
            ans=max(b+d+e+f,ans)

            ans=max(a+b+c+d,ans)
            ans=max(a+d+e+f,ans)
            ans=max(c+d+e+f,ans)
            ans=max(a+b+c+f,ans)

            ans=max(b+c+d+e,ans)
            ans=max(a+b+e+f,ans)
        #3x2
        if i<=(N-3) and j<=(M-2):
            a,b,c,d,e,f=tetris[i][j],tetris[i][j+1],tetris[i+1][j],tetris[i+1][j+1],tetris[i+2][j],tetris[i+2][j+1]
            ans=max(a+c+d+e,ans)
            ans=max(b+c+d+f,ans)

            ans=max(a+b+c+e,ans)
            ans=max(a+c+e+f,ans)
            ans=max(a+b+d+f,ans)
            ans=max(b+d+e+f,ans)

            ans=max(a+c+d+f,ans)
            ans=max(b+c+d+e,ans)
print(ans)

 

🎢 테트리스 4개 size로 나누어 분석

 

: 1~3번은 모양 그대로 확인 / 4번과 5번은 각각 8개의 테트리스 모양 구현

 

🎢 직접 위 모든 경우의 수 따져 최댓값 update

---

★ 1107 리모컨 ★

 

import sys
input=sys.stdin.readline
from itertools import product

N=int(input())
M=int(input())
A=abs(N-100) #1) only +, -
B=1_000_000

bs=[] #brokens
if M!=0:bs=list(map(int,input().split()))
ds={0,1,2,3,4,5,6,7,8,9}-set(bs) #digits

if len(str(N))>1:
    pos1=list(product(ds,repeat=len(str(N))-1))
else:
    pos1=[]
pos2=list(product(ds,repeat=len(str(N))))

if len(str(N))==6:
    pos3=[]
else:
    pos3=list(product(ds,repeat=len(str(N))+1))

for tup in pos1+pos2+pos3:
    n = int(''.join(map(str, tup)))
    B=min(B,len(str(n))+abs(n-N))

print(min(A,B))

 

🎢 원하는 번호로 이동하는 경우의 수는 (1) 인접 채널 번호 입력 뒤 + - 입력 (2) + -로만 입력

 

🎢 고장난 번호 제외 가능 버튼만으로 만들 수 있는 모든 숫자를 product()로 만들고 일일이 BF로 최소 case 찾기

(이 때 자릿수가 0이나 6이 아닌 경우 한 단계 적은 자릿수 / 높은 자릿수에서의 case도 product()로 만들고 일일이 찾기)

 

🎢 itertools의 product() 함수 + product()의 결과 tuple을 자연수로 바꾸는 int(''.join(map(str,tup)))

(ex) (0, 0, 0, 3, 3)은 00033이 아닌 33으로 바꿈)

---

★ 17779 게리맨더링 2 ★

 

import sys, copy
input=sys.stdin.readline
N=int(input())
arr,total,ans=[],0,10*100

def get_area(arr,s,e,d1,d2,total):
    a1,a2,a3,a4,a5=0,0,0,0,0
    #mark ! in area 5 border
    for x in range(d1+1):
        if 0<=(s+x)<N and 0<=(e-x)<N:
            arr[s+x][e-x] = '!'
        if 0<=(s+d2+x)<N and 0<=(e+d2-x)<N:
            arr[s+d2+x][e+d2-x] = '!'
    for x in range(d2+1):
        if 0<=(s+x)<N and 0<=(e+x)<N:
            arr[s+x][e+x] = '!'
        if 0<=(s+d1+x)<N and 0<=(e-d1+x)<N:
            arr[s+d1+x][e-d1+x] = '!'

    #mark ! in inner area 5
    for x in range(s,s+d1+d2+1):
        if x==s or x==(s+d1+d2):
            continue #already marked (area 5 only once in a row)
        cnt=2
        for y in range(N):
            if arr[x][y] == '!':
                cnt-=1            
            if cnt == 0:
                break
            if cnt==1:
                arr[x][y] = '!'

    for x in range(N):
        for y in range(N):
            if x<(s+d1) and y<=e:
                if arr[x][y] != '!': a1+=arr[x][y]
            if x<=(s+d2) and e<y<=(N-1):
                if arr[x][y] != '!': a2+=arr[x][y]
            if (s+d1)<=x<=(N-1) and y<(e-d1+d2):
                if arr[x][y] != '!': a3+=arr[x][y]
            if (s+d2)<x<=(N-1) and (e-d1+d2)<=y<=(N-1):
                if arr[x][y] != '!': a4+=arr[x][y]
    a5=total-(a1+a2+a3+a4)
    return (a1,a2,a3,a4,a5)

for _ in range(N):
    r=list(map(int,input().split()))
    arr.append(r)
    total+=sum(r)

for x in range(0,N):
    for y in range(1,N):
        for d1 in range(1,N+1):
            for d2 in range(1,N+1):
                if (0<=x<(x+d1+d2)<=(N-1)) and (0<=(y-d1)<y<(y+d2)<=(N-1)):
                    a1,a2,a3,a4=0,0,0,0
                    new_arr = copy.deepcopy(arr) #copying arr every time
                    tup_areas=get_area(new_arr,x,y,d1,d2,total)
                    ans=min(ans,max(tup_areas)-min(tup_areas)) #update
print(ans)

 

🎢 idea: 먼저 a5 영역에 ! 표시 → a1 / a2 / a3 / a4 영역 traversing 진행하면서 !가 아니라면 각각 count

 

※ 이 때 x,y 모두 index 0 ~ N-1 범위 if문 조건 (문제에서는 (x,y) 좌표 1부터 시작하고 (0,0)은 왼쪽 위에서 시작. x는 아래쪽, y는 오른쪽 진행이기에 문제 상의 좌표와 index 혼동 맞출 필요)

 

🎢 area 5 정하기

① border + ② inner part 정하기

: border 먼저 if문 네 번 돌리며 ! marking → for loop s부터 s+d1+d2까지 위의 행부터 차례대로 돌리기 → s+1행부터 s+d1+d2-1행까지는 cnt 2에서 0되기 전, 즉 cnt == 1일때 inner ! marking

 

🎢 매번 원래 array에서 진행해야 하므로 deepcopy()

 

🎢 total에서 최종적으로 구한 a1 ~ a4 뺀 남은 영역 a5 결정

---