[백준/Python] 1895 필터, 14888 연산자 끼워넣기

잡설

예전에 풀었던 문제들 다시 풀어봤다. 그냥 푸는것보다 예전보다 빠르거나 숏코딩으로 짜보는 것도 재미있을 것 같아서 옛날에 짠 코드들을 비교해보면서 짜보았다.

문제

1895 필터

풀이

단순하게 3*3 기준으로 생각해보면, 가장자리를 제외한 1~n-1, 1~m-1의 좌표와 그 좌표 주변의 값들만 확인하면 된다. dx, dy를 능숙하게 다룰 수 있는 사람이라면 해당 개념을 이용해 간단하게 해결할 수 있다. 값들의 크기가 그리 크지 않아서 단순하게 매번 배열을 새로 만들던, 슬라이싱을 하던 상관 없이 해결 할 수 있다.

코드

n,m=map(int,input().split())
a=[input().split()for i in range(n)]
x=[0,0,0,1,1,1,-1,-1,-1]
y=[0,1,-1,1,0,-1,1,0,-1]
t=int(input())
s=0
for i in range(1,n-1):
    for j in range(1,m-1):
        s+=sorted([int(a[i+y[d]][j+x[d]])for d in range(9)])[4]>=t
print(s)

잡기술

알아도 쓸모는 없지만, 2차원 배열을 1차원 배열처럼 활용해본적 있는 사람이라면 아이디어를 떠올릴 수 있는 방법이 있다. 굳이 dx,dy를 쓰지 않아도 동일한 기능을 만들 수 있는데,

(arr[i-1+d//3][j-1+d%3])for d in range(9)
이렇게 구현 할 수 있다. 몫과 나머지는 모두 0,1,2 중 하나의 값을 갖게 되고, 9까지 진행하면 각각 0,1,2의 반복과 000111222이렇게 반복이 된다. 이것을 -1과 더해주면 -1 0 1 이렇게 값이 변하게 되면서 9방향 탐색을 가능하게 한다.

잡기술과 코드를 이상하게 짜서 아래와 같이 숏코딩을 할 수 있다. (좋은 방법 아님)

숏코딩 성공!

J,I=int,input;n,m=map(J,I().split());a=[I().split()for _ in[0]*n];t=J(I());print(sum(sorted([J(a[i-1+d//3][j-1+d%3])for d in range(9)])[4]>=t for i in range(1,n-1)for j in range(1,m-1)))

 

문제

14888 연산자 끼워넣기

풀이

대략적으로 시간복잡도를 계산해보면, 선택지 4개가 최대 10칸(11개의 숫자 사이)에 들어갈 수 있으므로 4^10 대충 2^20이라 생각하면 1000*1000 정도 될 것이다. 실제로는 뒤로가면 남아있는 연산자가 0개인 연산자들이 생기므로 실제 시행 횟수는 저보다도 적을 것이다. 따라서 완전탐색으로 충분히 돌아가는 횟수이므로 완전탐색을 떠올릴 수 있다.

또한 매번 선택지가 분기한다고 생각하면 for문 보다는 재귀를 쓰는 쪽이 나을 것이다. 10중 for문을 쓰고 싶은게 아니라면,
permutations를 사용하는 것도 하나의 방법이 될 수 있다. + + + - - / 이렇게 있으면 여기서 permutation을 통해 모든 경우를 구하는 방법으로 활용할 수도 있다.

재귀로 코드를 구현한다면, 구현상 중요한 것은 최솟값과 최댓값의 갱신과 남아있는 연산자들의 개수 관리이다. 인자로 넘겨서 계산할 수 도 있고, 밖으로 빼서 계산할 수 도 있다.

코드

3년전에 풀었던 코드

#https://www.acmicpc.net/problem/14888

from sys import stdin
input=stdin.readline

n=int(input())

sootja=list(map(int,input().split()))

pl,mi,mu,di=list(map(int,input().split()))

mn=1000000000
mx=-1000000000

def compute(arr,plus,minus,mult,divi):
    global mn,mx
    if len(arr)==1:
        mn=min(arr[0],mn)
        mx=max(arr[0],mx)
        return
    if plus:
        compute([arr[0]+arr[1]]+arr[2:],plus-1,minus,mult,divi)
    if minus:
        compute([arr[0]-arr[1]]+arr[2:],plus,minus-1,mult,divi)
    if mult:
        compute([arr[0]*arr[1]]+arr[2:],plus,minus,mult-1,divi)
    if divi:
        if arr[0]<0:
            arr[0]=-arr[0]
            compute([-(arr[0]//arr[1])]+arr[2:],plus,minus,mult,divi-1)
        else:
            compute([arr[0]//arr[1]]+arr[2:],plus,minus,mult,divi-1)

compute(sootja,pl,mi,mu,di)

print(mx)
print(mn)

아마 이때는 검색을 통해서 짰던 코드로 기억한다. 위와 같이 인자로 넘겨서 코드를 작성할 수 있다. 개인적으로는 가독성은 제일 좋은 것 같다. (60ms)

from sys import stdin
input=stdin.readline

def bt(num,dep):
    global mn,mx
    if dep==n:
        mn=min(num,mn)
        mx=max(num,mx)
        return
    for i in range(3):
        if sachik[i]:
            newnum=eval(str(num)+sts[i]+str(sootja[dep]))
            sachik[i]-=1
            bt(newnum,dep+1)
            sachik[i]+=1
    if sachik[3]:
        sachik[3]-=1
        if num<0:
            bt(-(-num//sootja[dep]),dep+1)
        else:
            bt(num//sootja[dep],dep+1)
        sachik[3]+=1

n=int(input())
sootja=list(map(int,input().split()))
sachik=list(map(int,input().split()))
sts={0:'+',1:'-',2:'*'}

mx=-1e10
mn=1e10
bt(sootja[0],1)

print(mx,mn,sep='\n')

1년전에 짰던 코드, if를 안쓴다고 eval같은 걸 쓰고 있다. 구현상으로는 편하겠다고 썼던 것 같은데 여러모로 최악의 코드인 것 같다. 심지어 3년전 코드보다 한참 느리다.(500ms)

from sys import stdin
input=stdin.readline

def bt(num,dep):
    global mn,mx
    if dep==n:
        mn=min(num,mn)
        mx=max(num,mx)
        return
    for i in range(4):
        if sachik[i]:
            sachik[i]-=1
            bt(sts[i](num,sootja[dep]),dep+1)
            sachik[i]+=1

n=int(input())
sootja=list(map(int,input().split()))
sachik=list(map(int,input().split()))
sts=[lambda x,y: x+y,lambda x,y: x-y,lambda x,y: x*y,lambda x,y:x//y if x>0 else -(-x//y)]

mx=-1e9
mn=1e9
bt(sootja[0],1)

print(mx,mn,sep='\n')

비교적 최근에 짠 코드, 배열에 람다식을 집어넣어 if문을 덜 쓴 코드. 속도는 유의미한 차이는 없지만 조금 더 빠르다.