BAEKJOON : 14225, 16197

No. 14225

1. Problem

2. My Solution

• 비트마스크 이용
• Python3 5000ms, PyPy3 500ms

import sys

n = int(sys.stdin.readline())
seq = list(map(int,sys.stdin.readline().rstrip().split()))
check_num = [False] * ((n*100000)+1)

for i in range(1,1<<n):
    sum = 0
    for j in range(20):
        if i & (1<<j) == 0:
            continue
        else:
            sum += seq[j]
    check_num[sum] = True

for i in range(1,len(check_num)):
    if check_num[i] == True:
        continue
    else:
        print(i)
        break

3. Others' solutions

• DFS 이용 -> 500ms (Python3)
• 수열의 원소를 포함하는 경우와 포함하지 않는 경우로 나뉨
• DFS 를 통해 지나가는 경로마다 sum 을 저장

import sys

def dfs(idx,sum):

    if sum > 0:
        check_num[sum] = True

    if idx >= n:
        return

    dfs(idx+1, sum)
    dfs(idx+1, sum+seq[idx])


n = int(sys.stdin.readline())
seq = list(map(int,sys.stdin.readline().rstrip().split()))
check_num = [False] * ((n*100000)+1)

dfs(0,0)

for i in range(1,len(check_num)):
    if check_num[i] == True:
        continue
    else:
        print(i)
        break

4. Learned

• 부분 집합을 구하는 방법은 비트마스크 외에 DFS 도 가능함
• DFS 방식은 Combination 조합 방식에서 단계마다 값을 저장 (정해진 자릿수가 아닌 append 이용)

---

No. 16197

1. Problem

2. Others' Solutions

• 두개의 동전을 동시에 움직이도록 두개의 좌표를 queue 에 삽입
• # 벽에 막히는 경우는 같은 좌표를 다시 queue 에 삽입
• depth >= 10 인 경우는 10번 버튼을 눌렀다는 의미이므로 return -1

import sys
from collections import deque

def bfs():
  
    queue = deque()
    queue.append(coin + [0])
   
    while(queue):
        x1,y1,x2,y2,depth = queue.popleft()

        if depth >= 11:
            return -1

        for dx,dy in move:
            nx1 = x1 + dx
            ny1 = y1 + dy
            nx2 = x2 + dx
            ny2 = y2 + dy

            if (0 <= nx1 < n and 0 <= ny1 < m) and (0 <= nx2 < n and 0 <= ny2 < m):
                if board[nx1][ny1] == '#':
                    nx1, ny1 = x1, y1
                if board[nx2][ny2] == '#':
                    nx2, ny2 = x2, y2
                queue.append((nx1,ny1,nx2,ny2,depth+1))
            elif (0 <= nx1 < n and 0 <= ny1 < m) or (0 <= nx2 < n and 0 <= ny2 < m):
                return depth+1
            else:
                continue
    return -1
           
n,m = map(int,sys.stdin.readline().rstrip().split())
board = []
coin = []
move = [(-1,0),(1,0),(0,-1),(0,1)]

for _ in range(n):
    board.append(list(sys.stdin.readline().rstrip()))

for i in range(n):
    for j in range(m):
        if board[i][j] == 'o':
            coin.extend([i,j])

print(bfs())

3. Learned

• bfs 를 수행할 때 2개의 좌표를 기준으로 움직이기 위해서는 2개의 좌표를 queue 에 삽입하면됨