2019.03.22) 소프트웨어 마에스트로 마지막 스퍼트 3편(탐색) - 1987, 2294 (PyPy3)

테스트 시험을 봐봤는데 다들 쉬웠다.

물론 본시험은 어렵겠지만.. 열심히 해보도록하자.

1987번

R, C = map(int, input().split(' '))
 
ma = list()
 
for _ in range(R):
    ma.append(list(input()))
 
visited = dict()
 
stack = list()
stack.append(((0, 0), {ma[0][0]}, 1))
 
result = 0
while stack:
    (i, j), his, w = stack.pop()
    result = max(result, w)
 
    if i > 0:
        if not ma[i - 1][j] in his:
            tmp = his.copy()
            tmp.add(ma[i - 1][j])
            stack.append(((i - 1, j), tmp, w + 1))
    if j > 0:
        if not ma[i][j - 1] in his:
            tmp = his.copy()
            tmp.add(ma[i][j - 1])
            stack.append(((i, j - 1), tmp, w + 1))
    if i < R - 1:
        if not ma[i + 1][j] in his:
            tmp = his.copy()
            tmp.add(ma[i + 1][j])
            stack.append(((i + 1, j), tmp, w + 1))
    if j < C - 1:
        if not ma[i][j + 1] in his:
            tmp = his.copy()
            tmp.add(ma[i][j + 1])
            stack.append(((i, j + 1), tmp, w + 1))
 
print(result)
 

2294번

n, k = map(int, input().split())
li = [int(input()) for i in range(n)]
 
 
INF = 1e9
 
li.sort()
 
re = INF
 
stack = list()
 
stack.append((k, 0))
 
check = [INF for _ in range(k + 1)]
 
while stack:
    now, w = stack.pop()
    if check[now] < w:
        continue
    for i in li:
        for j in range(now // i + 1):
            nxt_n = now - i * j
            nxt_w = w + j
            if check[nxt_n] > nxt_w:
                stack.append((nxt_n, nxt_w))
                check[nxt_n] = nxt_w
r = check[0]
if r == INF:
    print(-1)
else:
    print(r)