log 2021-10-07

---

• sport
  • bj 2800 - 괄호 제거
  • bj 1817 - 짐 챙기는 숌

sport

bj 2800 - 괄호 제거

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

괄호 쌍이 많아야 10개라면, 지우는 경우의 수는 2^10 = 1024가지이다.

문제는, 어떤 식으로 정보를 저장해서 관리하고, 지운 수식들을 생성할지이다.

python solution

스택, 완전 탐색 + 딕셔너리 이용하여 풀었다. 각 괄호를 사용할 지 아닐지 관리하는 use 배열과, 각 문자 위치에 대해 그 위치가 어느 use 배열의 위치에 해당하는지 나타내는 사전이 있으면, 완전탐색으로 모든 조합을 만들 수 있고, 해당 사전은 먼저 스택을 이용하여 만들 수 있다.

def solve():
    ss=rsa()[0]
    ll=len(ss)
    ansset = set()
    # whether to use idx
    use = [0] * (11)
    # pointer to start/end paren
    dic = {}
    # position to use idx
    revDic = {}
    cnt = 0
    
    def dfs(lvl):
        if(lvl>cnt):
            # make val
            vals = []
            for i,ch in enumerate(ss):
                if(ch!='(' and ch!=')'):
                    vals.append(str(ch))
                elif(use[revDic[i]] == 1):
                    vals.append(str(ch))
            ansset.add(''.join(vals))
            return
        
        # pick lvl's use
        use[lvl]=1
        dfs(lvl+1)

        # unpick lvl's
        use[lvl]=0
        dfs(lvl+1)
        pass
    
    st=[]

    posset = []
    
    for i,ch in enumerate(ss):
        if(ch=='('):
            st.append(i)
        elif(ch==')'):
            la=st.pop()
            # print(la)
            posset.append([la, i])
            dic[cnt]=[la, i]
            revDic[la] = cnt
            revDic[i] = cnt
            cnt+=1
    # print(posset)
    dfs(0)
    for i,ans in enumerate(sorted(list(ansset))[1:]):
        print(ans)
    pass

bj 1817 - 짐 챙기는 숌

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

쉽지만 예외처리를 생각해야 하는 문제.

python solution

2번 틀림.

1. N=0일 때에는 추가적 배열 입력이 없으므로 읽어들이려 하면 런타임 에러가 나게 된다.
2. N=0일 때에는 책의 무게가 0이거나 한 게 아니라, 보낼 책이 없는 상황이므로 박스도 필요하지 않다.

def solve():
    N,MAX_SIZE = ria()
    cnt = 0
    curSize = 0
    if(N==0):
        print('0')
        return
    arr = ria()
    for i,itemSize in enumerate(arr):
        if(curSize+itemSize>MAX_SIZE):
            curSize=itemSize
            cnt+=1
        else:
            curSize+=itemSize
    if(curSize>0):
        cnt+=1
    print(cnt)
    pass

---